We have seen in the previous post that we can divide a problem into smaller similar ones, in order to avoid lengthy and confusing code. Quicksort adopts a similar approach. Although it has same performance as Merge Sort, it is very easy to implement.
Despite being so simple, Quicksort has average time performance of
O( n log(n) ).
Quicksort uses recursion to repeatedly sort subsets of the original data list. Quicksort, first, chooses a key or a pivot value. Then, it compares all the values with the key, and decide which values will go to the right and which to the left. The values smaller than the key are placed no the right and other no left half. As the left and right groups are made up in the order they are fed into the algorithm, they are not sorted. The algorithm then goes about sorting the left and the right group, this requires a recursive call to Quicksort. This goes on until there’s one value left in each group. After that, the
right - key - left are combined while moving up the hierarchy of recursive calls.
The following animation is using Hoare Partition scheme, in which a pair of values is used to sort the list.
The implement of Quicksort is pretty straightforward and easy to understand. There’s point to note that
equal is a list because the key may be repeated multiple times in given data.
def quick_sort( values ): n = len( values ) #s ize if n is 1 or not values: # c'mon, who sorts no or one value! return values pivot = values[ n//2 ] # choosing middle one as true pivot right =  left =  equal =  # handy for list appending for i in values: if i is pivot: equal.append(i) elif i > pivot: right.append(i) elif i < pivot: left.append(i) '''recursive call sorts the left and right groups. This goes on and on, and the groups get smaller down the hierarchy. Recursion automatically sorts the group without having to compare each value with the rest.''' return quick_sort(left) + equal + quick_sort(right)