Question

Comparing (Sort Algorithms)

Both of the two sorting algorithms will do "sort" on arrays which would contain x randomly generated integers where the value of x would be 10000, 20000, 40000 and 80000 (inputs).

The parts of the program should be followed as.....

1. Set x = 10000, randomly generate x integers. Call qsort function to sort these integers and get the execution time.

2. Randomly generate another x integers. Call your own sorting algorithm and get the execution time.

3. Print the above two execution time on the screen. Program terminates if x = 80000, otherwise set x = x * 2.

Answer 1

Editable code

Program

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <time.h>

void Bubble_Sort(int* n, int size) {

       int t;

       for (int i = 1; i < size; i++) {

              for (int j = 0; j < size - i; j++) {

                     if (n[j] > n[j + 1]) {

                           t = n[j];

                           n[j] = n[j + 1];

                           n[j + 1] = t;

                     }

              }

       }

}

void Swap(int *X, int *Y)

{

       int Temp = *X;

       *X = *Y;

       *Y = Temp;

}

void Randomize_Array(int* Number, int N)

{

       srand(10);

       for (int i = 0; i < N; ++i)

       {

              int R = rand() % 100;

              Swap(&Number[i], &Number[R]);

       }

}

int cmp(const void *P, const void *Q)

{

       int *P1, *Q1;

       P1 = (int *)P;

       Q1 = (int *)Q;

       return *P1 > *Q1;

}

int main()

{

       int* Array = NULL;

       for (int x = 10000;x <= 80000;x = x * 2)

       {

              Array = new int[x];

              int N = x;

              int Temp = N;

              for (int i = 0; i < N; ++i)

              {

                     Array[i] = Temp--;

              }

              clock_t T1, T2;

              Randomize_Array(Array, N);

              T1 = clock();

              Bubble_Sort(Array, N);

              T2 = clock();

             

              printf("\n\n\n");

              printf("The Bubble Sort execution time for x = %d is %lf ", x, (T2 - T1) / (float)CLOCKS_PER_SEC);

              T1 = clock();

              qsort(Array, N, sizeof(int), cmp);

              T2 = clock();

              printf("\nThe Quick Sort execution time for x = %d is %lf ", x, (T2 - T1) / (float)CLOCKS_PER_SEC);

       }

       printf("\n\n\n");

       system("pause");

       return 0;

}