Title: Compare sorting algorithms in C#, part 4 of 5 (Quicksort)

Quicksort

Quicksort is a recursive algorithm that uses a divide-and-conquer technique. While the list of items to be sorted contains at least two items, Quicksort divides it into two sublists and recursively calls itself to sort the sublists.

The Quicksort method first checks to see if the list it is sorting contains fewer than two items. If so, it simply returns because a list containing zero or one items is already sorted.

if the list contains two or more items, the method picks an item from the array to use as a dividing item. It then moves all of the items that belong before this dividing item in the left part of the array, and it places all of the other items in right part of the array. The method then recursively calls itself to sort two smaller sublists.

There are several ways in which the Quicksort method might pick the dividing item. One of the easiest is to simply use the first item in the sublist being sorted. If the list is initially arranged randomly, that item will probably be a reasonable choice. Chances are good that the item will belong somewhere in the middle of the sorted list so the two sublists the algorithm creates will be reasonably equal in size.

However, if the numbers are initially sorted or almost sorted, or if they are initially sorted in reverse order, then this method fails miserably. In that case the first item in the list will divide the list into one sublist that contains almost every item and another that contains almost no items. Since the larger sublist does not shrink much, the algorithm makes little headway.

In this case the algorithm will require on the order of N² steps. This is the same order of performance given by Selectionsort, but this algorithm is much more complicated so it's even slower.

A better method for selecting the dividing item is to choose one randomly. Then no matter how the items in the list are initially arranged, chances are good that the selected item will belong somewhere in the middle of the sorted list and the sublists will be fairly evenly sized.

As long as the sublists are fairly equal in size, the algorithm will require on the order of N * log(N) steps. It can be proven that this is the fastest time possible for a sorting algorithm that sorts by using comparisons. By adding a little randomness, this algorithm avoids the possibility of its worst case N² behavior and gives an expected case performance of N * log(N).

Quicksort is very fast in practice as well as theory, so it is the favorite sorting algorithm of many programmers. For all of these reasons, I'm also pretty sure it's the algorithm used by the Array.Sort method.

The following code shows the example program's method that starts the Quicksort algorithm. This is the method that the program passes into the RunAlgorithm method.

// Quicksort. private void Quicksort(int[] values) { Quicksort(values, 0, NumItems - 1); }

This code simply calls an overloaded version of the Quicksort method that takes as parameters the array of values, and the indexes of the first and last items that the method should sort. Those indexes tell the method which part of the array represents the sublist that it should sort.

The following code shows the version of the Quicksort method that takes those indexes as parameters.

// Use Quicksort to recursively sort // the items with indexes min <= i <= max. private void Quicksort(int[] values, int min, int max) { // If the list has no more than 1 element, it's sorted. if (min >= max) return; // Pick a dividing item. int i = Rand.Next(min, max + 1); int med_value = values[i]; // Swap it to the front so we can find it easily. values[i] = values[min]; // Move the items smaller than this into the left // half of the list. Move the others into the right. int lo = min; int hi = max; for (;;) { // Look down from hi for a value < med_value. while (values[hi] >= med_value) { hi--; if (hi <= lo) break; } if (hi <= lo) { values[lo] = med_value; break; } // Swap the lo and hi values. values[lo] = values[hi]; // Look up from lo for a value >= med_value. lo++; while (values[lo] < med_value) { lo++; if (lo >= hi) break; } if (lo >= hi) { lo = hi; values[hi] = med_value; break; } // Swap the lo and hi values. values[hi] = values[lo]; } // Sort the two sublists Quicksort(values, min, lo - 1); Quicksort(values, lo + 1, max); }

This code follows the description shown earlier. It picks a dividing item, moves the items to either side of that item, and then calls the method recursively to sort the two sublists.

Although I think Array.Sort uses the Quicksort algorithm, its implementation is better than the one I can build in C# code so it is consistently faster.

Download the example to experiment with it and to see additional details.