Quick sort is not the most efficient in many situations. It’s not the implementation of sort() in many popular languages. Yet, it’s the most valuable sort to learn, primarily because of interview. I think quicksort is a good test of coding abilities. The challenges:
#1 high-level goal of first pass — hard to remember!
#2 the gist of the first pass
#3 implementation in any language — many pitfalls
- pivot Object — the first object in a section can be designated the pivot object. Some people use the last object or a random object within the section. To keep things simple, we will assume the values are unique
- final resting place — goal is to put the pivot object into its final resting place within the section, using scan-and-swap
- swaps — are the mechanism of movements
- scan — you must scan in some direction
- partition — after the first pass, the pivot object is in its final resting place and all smaller objects are on its left.
First we need to understand the high-level goal. Then the next challenge is the partition algorithm. The only way to remember the implementation details is writing the code.
On P 146 [[introduction to algorithms]], the procedure partition(A,p,r) does the following on the Section A[p,r] inclusive.
- it moves the rightmost (pivot) object from r to the grave/anchor position within the section
- it keeps the rightmost object value as the benchmark value throughout the procedure.
- it returns the new index of this object. The index is defined in the entire array A.
- it shuffles 0 or more elements within the section
- it doesn’t try to sort any subsection
Upon receiving an unsorted section, the procedure simply puts the rightmost thingy into the grave position within the section.
Corollary: first scene in the quicksort movie actually completes the job of putting the rightmost object into its final resting place as an anchor within the entire array. After that, we focus on sorting the “left-section” and the “right-section” (in separate threads) without worrying about the first anchor object. Within the left-section, first scene completes the job of putting the rightmost object into its grave, a final resting place within the entire array.
Coding note — the recursion is not using a single function name like A calling A itself. Instead, qsort() calls partition() then qsort(). Most of the work is in partition().
Coding note — partition() function isn’t recursive in itself.