I have code for quicksort and mergesort, and I put a global counter variable, which increments by each iteration (comparison). I would suggest that this would be consistent with my crude asymptotic analysis. It does for merge sorting, but for quicksort it doesn't. I do not understand why. I select the last element of the input array - this is the pivot point at each iteration. I know this is not optimal, but it is not important for this discussion. Since I select the last element, I would expect both arrays with ascending and descending orders to lead to a comparison of O (n ^ 2). To be more specific, I would expect the number of comparisons to be n to choose 2, because you add n + n-1 + n-2 + n-3 + .... + 1 in the worst case. But this does not seem to be happening.
With an input size of 100,000, when entering, sorted in descending order, I get 705 082 704 iterations. I get the same number for the input array, sorted in ascending order. But 100,000 choose 2 is about 5 billion. Why the discrepancy?
To sort a merge with an input of 100,000, I get about 1.6 million iterations, which is apparently correct.
Below is the code that includes my implementation of quicksort, as well as my counting technique, both of which can be disabled and thus cause this mismatch. Otherwise, my logic must be erroneous as to how many iterations this should take?
In addition, strangely enough, I am curious that, although the number of comparisons is the same in the upstream and downstream input arrays, the increasing version is 2-3 times faster. What could explain this. Without further ado, there is a code.
int counter = 0; int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int partition(int *array, int low, int high){ int firsthigh = low; int pivot = high; for(int i = low; i < high; i++) { counter++; if(array[i] < array[pivot]) { swap(array[i], array[firsthigh]); firsthigh++; } } swap(array[pivot],array[firsthigh]); return firsthigh; } void quicksort(int *array, int low, int high){ int p; if(low < high) { p = partition(array, low, high); quicksort(array, low, p-1); quicksort(array,p+1,high); } } int main(){ int array[100000]; for(int i = 0; i < 100000; i++) array[i] = i; struct timeval start, end; for(int i = 0; i < 100000; i++) cout << array[i] << " "; gettimeofday(&start, NULL);