CODEWITHSUNDEEP
c++calgorithmsortingquicksort
ordinary
ordinary

Reputation: 6133

Why does quicksort take longer when sorted in descending order vs ascending order

I have code for quicksort and mergesort, and I've placed a global counter variable that gets incremented for every iteration(comparison) that is made. I would assume this would correspond to my rough asymptotic analysis. For merge sort it does, but for quicksort it doesn't. I don't understand why. I'm choosing the last element of the input array is the pivot in every iteration. I know that this is non-optimal, but that doesn't matter for the sake of this discussion. Since I'm choosing the last element, I would expect that both ascending and descending order arrays would result in O(n^2) comparisons. To be more specific, I would expect that the number of comparisons would be n choose 2, because you are adding n + n-1 + n-2 + n-3 + .... + 1 in the worst case. But this does not seem to be happening.

On an input size of 100,000, with the input sorted in descending order I get 705,082,704 iterations counted. I get the same number for an input array sorted in ascending order. But 100,000 choose 2 is around 5 billion. Why the discrepancy?

For merge sort, with an input of 100,000, I get approx 1.6 million iterations, which is seemingly correct.

The following is the code which includes my implementation of quicksort as well as my counting technique, both of which may be off and thus causing this discrepancy. Otherwise it must be that my logic is wrong about how many iterations this should take?

Also, as an aside, its curious to me that although the number of comparisons are the same in both the ascending and descending input arrays, the ascending version is 2-3 times as fast. What could account for that. Without further ado here is the 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);

  //mergesort(array, 0, 99999);
  quicksort(array, 0, 99999);

  gettimeofday(&end, NULL);
  long long time =   (end.tv_sec * (unsigned int)1e6 +   end.tv_usec) -
                     (start.tv_sec * (unsigned int)1e6 + start.tv_usec);

  for(int i = 0; i < 100000; i++)
    cout << array[i] << " ";
  cout << endl;

  cout << endl << endl << time/1000000.0 << endl;
  cout << endl << counter;
}

Upvotes: 4

Views: 4275

Answers (1)

IVlad
IVlad

Reputation: 43477

  1. If you want to count the number of iterations of the inner for loop, use long long. n*(n-1)/2 overflows an int for n = 100 000. If you want to count swaps, you should increment your counter whenever a swap is being done.

  2. Two easy optimizations to make to this are:

There are others of course, but this should get you a decent algorithm.

Upvotes: 4

Related Questions