Thread: Quicksort's recursion

I'd like to point out a couple of things. First:

Originally Posted by thames

Code:

   srand(time(NULL));   
  
   pivot = a[rand() % size];

The above is wasteful. On every invocation, you'll reinitialize the random number generator, based on the current time in seconds. Because the function is called recursively, it will be called in rapid succession, and the rand() will always return the same value. So, it does not really yield a random pivot.

The median-of-three pivot selection is found to be just as good in practice. Basically, you take the first (a[0]), middle (a[size/2]), and last value (a[size-1]), sort the three, and use the middle one (the median of the three) as the pivot.

Second, your loop which moves values less than pivot to the beginning of the array and values greater than the pivot to the end of the array, does not handle pivots correctly. If you supply it with an array containing repeated values, like 1, 5, 1, 1, 5, 2, 2, 4, 4, 4, it will get stuck (at least some of the time).

You need to decide what you do with the pivot values and handle them accordingly.

The typical approach is to first swap the pivot with the final element in the array. After you have sorted the left side of the array, you swap the pivot just after the left side, and sort the rest of the array (not including the pivot). To do that, you can either swap a random index with the final element in the array and take the pivot value from the final element, or use the median-of-three pivot selection in a way that puts the middle value at the end of the array. I warmly recommend the median-of-three pivot selection over random pivot selection.