Quick Sort

Notes

Skiena Chapter 4

Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting.

Quick sort is a random algorithm. Whenever we deal with a random algorithm, we always want to think about what the worst case scenario is, and what we can do to avoid it. In the case of quicksort, the worst case scenario consists of bad choices for each pivot - namely, each pivot that is chosen happens to be right next to the prior pivot, so we are continually sorting things one at a time, making quick sort equivalent to Insertion Sort.

In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).