Part 3: Quick sort!

THE SORTENING

Quick sort is another divide-and-conquer sorting algorithm. It is different from merge sort in that it has no "merge" function and it does not form the sublists by simply halving the superlist. Quick sort chooses a "pivot," to which it compares each item in the list and places those items less than the pivot in one list, and those greater than (or equal to) in the other. Quick sort is then run on each list, and the results thereof are concatenated, with the pivot between them.



The algorithm:

1. Choose a pivot. This is best done randomly, but other options are possible, such as always choosing the first or middle item.
2. Partition the list. Each item less than the pivot goes in one list; each item greater in another list. Items equivalent to the pivot can go in either, so long as this is consistent. The choice of what to do with equivalent items is largely arbitrary.
3. Quick sort each list. Remember here that a list of length 1 or 0 is already sorted.
4. Now the first and second sublists are sorted, and the pivot is greater than the greatest item in the first and less than the least item in the second. The pivot is added to the end of the first list, which is then concatenated with the second, and we return the list we get from that.

Example:  [8, 14, 6, 9, 7]

Pivot: 9

First list: [8, 6, 7]   Second list: [14]

Quicksort the first list: 

Pivot: 7

First list: [6]   Second list: [8]

Now the first and second lists are already sorted (length 1), so we concatenate with the pivot in the middle: [6, 7, 8]

So now we back up a level; we've sorted the first list: 

[8, 6, 7] -> [6, 7, 8]

Quicksort the second list:

[14] is of length 1, therefore it is already sorted.

Concatenate (with the pivot (9) in the middle):

[6, 7, 8] + [9] +[14] = [6, 7, 8, 9, 14]

We have now sorted the list.

Quicksort also has O(nlgn) complexity (in average and best case scenarios), where the n comes from the n comparisons we make to partition the lists, and the lg(n) comes from the number of partitions we'll have to do. In the worst case, quick sort may have performance as poor as O(n^2); this occurs most often when sorting already sorted arrays with an algorithm that chooses the first or last element of a list as the pivot. (Because then the algorithm must make n comparisons in the partitioning, multiplied by the n levels of recursion that will be necessary.) This problem can be alleviated by choosing the pivot randomly, as we did in the example above.