Question

Using 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 first, 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 sublist reduces to less than 20, sort thesublis t using an insertion sort.
• d. Sort the array using pivot as the median of the first, 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 and print the CPU time for each of the preceding four steps. To find the current CPU time, declare a variable, say, x, of type clock_t.The statement x = clock(); stores the current CPU time in x. You can check the CPU time before and after a particular phase of a program. Then, to find the CPU time for that particular phase of the program, subtract the before time from the after time. Moreover, you must include the header file ctime to use the data type clock_t and the function clock. Use a random number generator to initially fill the array.

Answer 1

ANSWER:

Answer:

Note: Code has been implemented as per user requirements.

#include <sstream>

#include <fstream>

#include <iostream>

#include <ctime>

using namespace std;

//FUNCTION HEADERS

void qsMethodA(int *myQSList, int myStartInd, int myEndInd);

void qsMethodB(int *myQSList, int myStartInd, int myEndInd);

void qsMethodC(int *myQSList, int myStartInd, int myEndInd);

void qsMethodD(int *myQSList, int myStartInd, int myEndInd);

void insertionSort(int *myQSList, int myStartInd,int myEndInd);

//a. Sort the array using pivot as the middle element of the array.

void qsMethodA(int *myQSList, int myStartInd, int myEndInd)

{

//PIVOT IS THE MEDIAN OF FIRST ANDLAST ELEMENT

int myPivotInd = (myStartInd + myEndInd)/2;

int myInd = myStartInd;

//PARTITION THE LIST

if ( myStartInd < myEndInd )

{

  

int tmpValA = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myPivotInd];

myQSList[myPivotInd] = tmpValA;

//ARRANGE THE ELEMENTS IN UPPER AND LOWER SUBLIST   

for ( int ii = myStartInd + 1; ii <= myEndInd; ii++ )

{

  

if ( myQSList[ii] <= myQSList[myStartInd] )

{

myInd+=1;

int tmpValB = myQSList[ii];

myQSList[ii] = myQSList[myInd];

myQSList[myInd] = tmpValB;

}

}

  

int tmpValC = myQSList[myStartInd];

  

myQSList[myStartInd] = myQSList[myInd];

myQSList[myInd] = tmpValC;

  

myPivotInd = myInd;

//RECURSIVELY CALL THIS METHOD TO SORT FOR THE SUBLISTS

qsMethodA(myQSList,myStartInd,myPivotInd - 1); //LOWER SUBLIST

qsMethodA(myQSList,myPivotInd + 1,myEndInd);//UPPPER SUBLIST

  

  

}

}

//b. Sort the array using pivot as the median of the first, last, and middle elements of the array.

void qsMethodB(int *myQSList, int myStartInd, int myEndInd)

{

int m=(myStartInd+myEndInd)/2;

//PIVOT IS THE MEDIAN OF FIRST AND LAST AND MIDDLE ELEMENT

int myPivotInd = (myStartInd + myEndInd+m)/3;

int myInd = myStartInd;

//DIVIDE LIST INTO 2 HALVES   

if ( myStartInd < myEndInd )

{

  

int tmpValA = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myPivotInd];

myQSList[myPivotInd] = tmpValA;

//ARRANGE THE ELEMENTS   

for ( int ii = myStartInd + 1; ii <= myEndInd; ii++ )

{

  

if ( myQSList[ii] <= myQSList[myStartInd] )

{

myInd+=1;

int tmpValB = myQSList[ii];

myQSList[ii] = myQSList[myInd];

myQSList[myInd] = tmpValB;

}

}

  

int tmpValC = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myInd];

myQSList[myInd] = tmpValC;

  

myPivotInd = myInd;

//RECURSIVELY CALL THIS METHOD TO SORT FOR THE SUBLISTS

qsMethodB(myQSList,myStartInd,myPivotInd - 1);//LOWER SUBLIST

qsMethodB(myQSList,myPivotInd + 1,myEndInd);//UPPPER SUBLIST

  

}

}

//INSERTION SORT

void insertionSort(int *myQSList, int myStartInd,int myEndInd)

{

int ii, kk, jj;

for (ii = myStartInd+1; ii < myEndInd+1; ii++)

{

kk = myQSList[ii];

jj = ii-1;

  

while (jj >= 0 && myQSList[jj] > kk)

{

myQSList[jj+1] = myQSList[jj];

jj = jj-1;

}

myQSList[jj+1] = kk;

}

}

//c. Sort the array using pivot as the middle element of the array. How- ever, when the size of any sublist reduces to less than 20, sort the sublist using an insertion sort.

void qsMethodC(int *myQSList, int myStartInd, int myEndInd)

{

//PIVOT IS THE MEDIAN OF FIRST ANDLAST ELEMENT

int myPivotInd = (myStartInd + myEndInd)/2;

int myInd = myStartInd;

//IF NO OF ELEMENTS<20 SORT BY INSERTION SORT

if(myEndInd-myStartInd<20)

{

  

insertionSort(myQSList,myStartInd,myEndInd);

}

//WHEN NO OF ELEMENTS>=20 SORT BY QUICK SORT

//DIVIDE LIST

else if ( myStartInd < myEndInd )

{

  

int tmpValA = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myPivotInd];

myQSList[myPivotInd] = tmpValA;

for ( int ii = myStartInd + 1; ii <= myEndInd; ii++ )

{

  

if ( myQSList[ii] <= myQSList[myStartInd] )

{

myInd+=1;

int tmpValB = myQSList[ii];

myQSList[ii] = myQSList[myInd];

myQSList[myInd] = tmpValB;

}

}

  

int tmpValC = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myInd];

myQSList[myInd] = tmpValC;

  

myPivotInd = myInd;

//RECURSIVELY CALL THIS METHOD TO SORT FOR THE SUBLISTS

qsMethodC(myQSList,myStartInd,myPivotInd - 1);

qsMethodC(myQSList,myPivotInd + 1,myEndInd);

  

}

}

//d.Sort the array using pivot as the median of the first, 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.

void qsMethodD(int *myQSList, int myStartInd, int myEndInd)

{

  

int m=(myStartInd+myEndInd)/2;

//PIVOT IS THE MEDIAN OF FIRST AND LAST AND MIDDLE ELEMENT

int myPivotInd = (myStartInd + myEndInd+m)/3;

int myInd = myStartInd;

//IF NO OF ELEMENTS<20 SORT BY INSERTION SORT

if(myEndInd-myStartInd<20)

{   

insertionSort(myQSList,myStartInd,myEndInd);

}

//WHEN NO OF ELEMENTS>=20 SORT BY QUICK SORT

//DIVIDE LIST

else if ( myStartInd < myEndInd )

{

int tmpValA = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myPivotInd];

myQSList[myPivotInd] = tmpValA;

  

for ( int ii = myStartInd + 1; ii <= myEndInd; ii++ )

{

  

if ( myQSList[ii] <= myQSList[myStartInd] )

{

myInd+=1;

int tmpValB = myQSList[ii];

myQSList[ii] = myQSList[myInd];

myQSList[myInd] = tmpValB;

}

}

  

int tmpValC = myQSList[myStartInd];

myQSList[myStartInd] = myQSList[myInd];

myQSList[myInd] = tmpValC;

  

myPivotInd = myInd;

//RECURSIVELY CALL THIS METHOD TO SORT FOR THE SUBLISTS

qsMethodD(myQSList,myStartInd,myPivotInd - 1);

qsMethodD(myQSList,myPivotInd + 1,myEndInd);

  

}

}

//PRINT THE LIST

void printmyQSList(int *myQSList,int myListSize)

{

for ( int ii = 0; ii < myListSize; ii++ )

{

cout<<myQSList[ii]<<" ";

}

cout<<endl;

}

int main()

{

  

srand(time(NULL));

int myListSize = 1000000;

int *myQSList = new int[myListSize];

//GENERATE RANDOMNUMBERS TO FILL ARRAY

for ( int ii = 0; ii < myListSize; ii++ )

{

myQSList[ii]=rand()%1000000+1;

}

//COPY THE LIST INTO THREE MORE LISTS

int *myQSList2=myQSList;

int *myQSList3=myQSList;

int *myQSList4=myQSList;

//OPTION e

//FIND SORT TIME FOR METHOD a

clock_t myStartTime = clock();

//CALLING METHOD A OF QUICK SORT

qsMethodA(myQSList, 0, myListSize - 1);

clock_t myEndTime = clock();

clock_t sortTime = double(myEndTime - myStartTime);

cout<<"After sorting by median of first and last"<<endl;

cout<<"Sort time:"<<sortTime<<" ms"<<endl;

//FIND SORT TIME FOR METHOD b

myStartTime = clock();

//CALLING METHOD b OF QUICK SORT

qsMethodB(myQSList2, 0, myListSize - 1);

myEndTime = clock();

sortTime = double(myEndTime - myStartTime);

cout<<"After sorting by median of first last middle"<<endl;

cout<<"Sort time:"<<sortTime<<" ms"<<endl;

//FIND SORT TIME FOR METHOD c

myStartTime = clock();

//CALLING METHOD c OF QUICK SORT

qsMethodC(myQSList3, 0, myListSize - 1);

myEndTime = clock();

sortTime = double(myEndTime - myStartTime);

cout<<"After sorting by median of first last and using insertion sort"<<endl;

cout<<"Sort time:"<<sortTime<<" ms"<<endl;

//FIND SORT TIME FOR METHOD d   

myStartTime = clock();

//CALLING METHOD d OF QUICK SORT

qsMethodD(myQSList4, 0, myListSize - 1);

myEndTime = clock();

sortTime = double(myEndTime - myStartTime);

cout<<"After sorting by median of first last middle and using insertion sort"<<endl;

cout<<"Sort time:"<<sortTime<<" ms"<<endl;

return 0;

}

Output: