Question

Using C++

Create a program that performs the Bubble Sort, the Insertion Sort, and the Selection Sort with arrays of varying lengths. You will time each algorithm.

The algorithms' time complexities should allow us to predict how these algorithms will perform.

Program needs

Four separate arrays, each with the same length and filled with the same sequence of randomly chosen numbers.

Four separate functions, one for each of the four algorithms.

All four functions will need to be timed. Be sure to only time the operations directly involved with the sorting algorithm’s code.

You will run your completed program five times, making note of the four run times produced from each algorithm.

• Run 1: Length of the arrays = 50000
• Run 2: Length of the arrays = 75000
• Run 3: Length of the arrays = 100000
• Run 4: Length of the arrays = 150000
• Run 5: Length of the arrays = 200000

Answer 1

Time required for each sorting algorithm(in seconds):

Bubble sort :
50000 : 14.67 sec, 14.50 sec, 14.59 sec, 14.96 sec
75000 : 32.04 sec, 32.82 sec, 33.50 sec, 33.14 sec
100000 : 63.32 sec, 63.57 sec, 62.20 sec, 62.03 sec
150000 : 136.64 sec, 140.31 sec, 139.63 sec, 137.96 sec
200000 : 254.18 sec, 252.64 sec, 259.21 sec, 253.93 sec

Insertion sort :
50000 : 2.34 sec, 1.95 sec, 1.90 sec, 1.93 sec
75000 : 4.43 sec, 4.35 sec, 4.46 sec, 4.37 sec
100000 : 7.68 sec, 8.06 sec, 8.72 sec, 7.41 sec
150000 : 17.88 sec, 18.02 sec, 18.18 sec, 17.95 sec
200000 : 34.43 sec, 33.17 sec, 31.93 sec, 33.87 sec

Selection sort :
50000 : 1.92 sec, 1.87 sec, 2.09 sec, 1.92 sec
75000 : 4.20 sec, 4.23 sec, 4.37 sec, 4.34 sec
100000 : 12.53 sec, 12.59 sec, 13.23 sec, 13.34 sec
150000 : 33.18 sec, 33.03 sec, 32.88 sec, 32.97 sec
200000 : 59.79 sec, 60.56 sec, 59.82 sec, 60.78 sec

The code used for comparison

void bubbleSort(int A[], int n)
{
    clock_t t;
    t = clock();
   for(int i = 0; i < n-1; i++)
       for(int j = 0; j < n-i-1; j++)
           if(A[j] > A[j+1])
               swap(A[j],A[j+1]);

    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
    printf("%f seconds to execute \n", time_taken);
}

void insertionSort(int A[], int n)
{
    clock_t t;
    t = clock();
   int key, j;
   for(int i = 1; i < n; i++)
   {
       key = A[i];
       j = i - 1;

       while(j >= 0 && A[j] > key)
       {
           A[j + 1] = A[j];
           j = j - 1;
       }
       A[j + 1] = key;
   }

    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
    printf("%f seconds to execute \n", time_taken);
}

void selectionSort(int A[], int n)
{
    clock_t t;
    t = clock();
   int min_idx;

   for(int i = 0; i < n-1; i++)
   {
       min_idx = i;
       for(int j = i+1; j < n; j++)
       if (A[j] < A[min_idx])
           min_idx = j;

       swap(A[min_idx],A[i]);
   }

    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC;
    printf("%f seconds to execute \n", time_taken);
}