//you can run this code on cpp.sh website to see the results. Every time the ratio is different but it should be near 0.9 #include #include #include #include using namespace std; int counter; //quicksort void quick_sort(int a[], int length) { if (length > 1) { int *left = a, *right = &a[length - 1], dir = 1; while (left != right) { if (*left * dir > *right * dir) { swap(*left, *right); swap(left, right); dir = -dir; } right -= dir; counter++; //called from global variable } quick_sort(a, left - a); quick_sort(left + 1, length - 1 - (left - a)); } } //Create array from 0 to n, then shuffle the elements int* makeRandomArray(int size) { int* a = new int[size]; for (int i = 0; i < size; i++) a[i] = i; srand(time(NULL)); random_shuffle(a, a + size); return a; } //printing the called array void print(int* a, int size) { for (int i = 0; i < size; i++) cout << a[i] << endl; cout << endl; } //Calculate the ratio of counter over (1.386 n lg n) double ratio(int size) { double value = (counter-1) / (1.386 * size * log2(size)); return value; } int main() { int size = 1000000; //The number of elements in array int* a = makeRandomArray(size); //print(a, size); //printing the random array quick_sort(a, size); //call the quicksort and sort it cout << endl << endl; cout << "//SORTED BY QUICKSORT\\\\"; cout << endl << endl; //print(a, size); //printing the sorted array cout << endl << endl; cout << "Key comparison: " << (counter-1); cout << endl << endl; cout << "Ratio is: " << ratio(size); cout << endl << endl; return 0; }

QuickSort Comparison Ratio