For a coder, understanding the Quicksort algorithm is like knowing the secret of 42—either you get it, or you don’t belong to the club. If you don’t know either, let’s work on the first one!
The Quicksort Algorithm — A Python Implementation
def qsort(L): # The empty list is sorted by default if L == []: return [] # Pivot is first element pivot = L[0:1] # Sort elements that are smaller than pivot left = qsort([x for x in L[1:] if x < L[0]]) # Sort elements that are larger or equal than pivot right = qsort([x for x in L[1:] if x >= L[0]]) # Concatenate the three parts to the sorted list # assuming left and right are already sorted recursively return left + pivot + right print(qsort([0,33,22]))
The algorithm is a variant of the popular Quicksort algorithm. The function qsort
sorts the list. But why?
Quicksort Explanation
Quicksort selects a pivot element from the list. In the code snippet, it selects the first element of the list using indexing, i.e., L[0]
.
- Then, the algorithm moves all elements that are smaller than the pivot to the left side.
- Similarly, it moves elements that are larger or equal than the pivot to the right side.
This is repeated in a recursive manner for the left and the right lists.
Suppose, you create a new list as follows. You put all elements that are smaller than the pivot on the left, then the pivot, then all elements that are larger or equal the pivot on the right. The resulting list feels a bit more sorted, right? If the two sublists were already sorted, the list would be perfectly sorted. This is where the recursive call of qsort
comes into play. It takes over the problem of sorting each sublist by applying the same scheme of pivoting and recursion to the sublist.
Here’s a visual explanation, I prepared as part of my book Python One-Liners:
Interactive Interpreter Quicksort
You can test this code in our interactive code shell:
Exercise: Try sorting a string list—does it work?
Code Puzzle Quicksort
Here’s a code puzzle regarding the Quicksort algorithm that you may enjoy—click the image to solve it in our interactive Finxter puzzle app:
Are you a master coder?
Test your skills now!