Question

I want to compare the runtimes and swap operations times among quick Sort, selection Sort and shell Sort

here is my code:

But when I create a 1000,000 size array, I can't get the result of the operations times and runtime. what's wrong with my code? and I also want to copy the array. Because I want to use same array for three sort. And for the shell Sort, I haven't learn it in my class. Can anyone help me to add this part?

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
static int count = 0;

int quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
//int count =0;
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
count++;
}
};

/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
return count;
}
int selectSort(int arr[], int n) {

int index_min_value;
int temp;
int count=0;
for (int i=0; i<n-1; i++) {
// outer loop tracks the sorted portion of the list
index_min_value = i; //set index_min_value to the current index of array
for (int j=i+1; j < n; j++) // inner loop finds the next smallest value
{
if (arr[j] < arr[index_min_value])
index_min_value = j;

}
if (index_min_value != i) {
temp = arr[i];
arr[i] = arr[index_min_value];
arr[index_min_value] = temp;
count++;
}
}
return count;
}
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void printList(int arr[], int length){
for (int i = 0; i<length; i++){
cout<<arr[i]<<" ";

}
cout<<endl;
}

int main(){
//HINT: You should place a counter into each algorithm to see how many time each of them run. Then you can compare them easier.
//You should use the given print statements for better organization.
int count = 0;
int myArray1[] = {12, 13, 5, 4, 7, 18, 9 };
int myArray2[] = {12, 13, 5, 4, 7, 18, 9 };
//selectSort
int start = clock();
count = selectSort(myArray1,7);
int stop = clock();

cout<<"When ordered with selectSort, after "<<count<<" operations the result is: "<<endl;
cout<< "time = " <<(stop-start)/double(CLOCKS_PER_SEC)*1000 << endl;
printList(myArray1,7);
int start1 = clock();
count = quickSort(myArray2,0,6);
int stop1 = clock();

cout<<"When ordered with quickSort, after "<<count<<" operations the result is: "<<endl;
cout<< "time1 = " <<(stop1-start1)/double(CLOCKS_PER_SEC)*1000 << endl;
printList(myArray2,7);
int *myArray3 = new int[10000000];
srand((unsigned)time(0));

for(int i=0; i<1000000; i++){
myArray3[i] = (rand()%10000)+1;

//cout << myArray5[i] << endl;
}
int start2 = clock();
count = selectSort(myArray3,1000000);
int stop2 = clock();
cout<<"When ordered with selectSort, after "<<count<<" operations the result is: "<<endl;
cout<< "time = " <<(stop2-start2)/double(CLOCKS_PER_SEC)*1000 << endl;
return 0;
}

Answer 1

PAvck= arr[high):