Section22.9QuickSort with Characters, and a Smarter Pivot
QuickSort doesn’t just work on numbers— as long as we have a way to compare two elements, we can sort anything. Let’s practice with an array of chars.
We’ll also address a weakness of the version of QuickSort we’ve used so far: always choosing the last element as the pivot works fine on average, but performs poorly when the list is already sorted (or nearly sorted), since the partitioning barely shrinks the list each time. A common fix is to use the median-of-three strategy: instead of always taking the last element, take the median of the first, last, and middle elements of the (sub)list as the pivot.
The two animations below start from the same, already-sorted list, side by side— one always pivoting on the last element, the other using median-of-three. Watch how much more work the plain version has to do:
Before partitioning, swap whichever of the first, last, and middle elements is the median of the three into the last position, so that value is used as the pivot.
