Question

Please include all .cpp/.h files if neccesary, this is in C++

Sort an array of 10,000 elements using the quick sort algorithm as follows:

a- sort the array using pivot as the middle element of the array.

b- Sort the array using pivot as the median of the fist,last and middle elements of the array .

c- sort the array using pivot as the middle element of the array.However ,when the size of any sub list reduces to less than 20 ,sort the sublist using an insertion sort .

d-Sort the using pivot as the median of the fist,last and middle elements of the array .When the size of any sublist reduces to less than 20 ,sort the sublist using an insertion sort.

e-Calculate the print the CPU time for each of the preceding four steps .

To find the current CPU time , declare a variable say x, of the type clock_t . The statement x= clock(); store the current CPU time in x .You can check the current CPU time before and after a particular phase of the program , subtract the before time from the after time .Moreover you must include the header file ctime to use the date type clock_t and the function clock . use a random generator to initially fill the array.

Any help is greatly appreciated, thank you.

Answer 1

#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

// insertion sort

void insertionSort(int array[], int first, int size) {
   int i, j, key;

   for (i = 1 + first; i < size + first; i++) {
       key = array[i];
       j = i - 1;

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

       array[j + 1] = key;
   }
}

// partition for quicksort
int partition(int array[], int first, int last) {

   // check partition size

if ((last - first) < 20) {
      
       insertionSort(array, first, (last - first + 1));
       // return middle
       return((last + first) / 2);
   }
   else {

       // using pivot
       int pivot = array[last];
       int index = (first - 1);

       for (int j = first; j<last; j++) {
           if (array[j]<pivot) {
               index++;

               int tmp = array[index];
               array[index] = array[j];
               array[j] = tmp;
           }
       }

       int temp = array[index + 1];
       array[index + 1] = array[last];
       array[last] = temp;

       return(index + 1);

   }

}

// quick sort calling

void quickSort(int array[], int first, int last) {
   if (first<last) {
       int pi = partition(array, first, last);

       quickSort(array, first, pi - 1);
       quickSort(array, pi + 1, last);
   }
}

// this function for print array

void print(int array[], int n) {

   for (int i = 0; i < n; i++) {
       if (i % 20 == 0) {
           cout << endl;
       }
       cout << array[i] << " ";
   }

}

int main() {

   int ary[10000];

   srand(time(0));

  
   // initialize by random numbers to array

   for (int i = 0; i<10000; i++) {
       ary[i] = rand();
   }

   //print(ary, 10000);
   //cout << endl << endl;

   clock_t start_ = clock();

   quickSort(ary, 0, 9999);

   clock_t end_ = clock();

   // cpu time
   cout << "Elapsed time in milliseconds : "
       << (end_ - start_)<< " ms" << endl;

   cout << endl << endl;

   //print(ary, 10000);

   system("pause");
   return(0);
}

c:\users\debojyoty chakravort documents\visual studio 2015 Projects\sortquick Debug\sortquick.exe Elapsed time in milliseconds : 1 ms Press any key to continue