Kodeclik Blog
Quicksort Primer
What is sorting?
Sorting is the task of arranging, in either increasing or decreasing order, a given set of numbers (or other orderable quantities) in an array. Sorting is an important task in computer science and considered to be among the most basic skills necessary for a programmer.
How does quicksort work?
Quicksort has some similar characteristics to merge sort. Like merge sort, it partitions the array into two parts, sorts each part and then combines the results. But the similarities stop there. Quicksort does more work before the partitioning so that the merging becomes easier, almost trivial.
We illustrate how quicksort works using a running example. We are given the array [35, 67, 12, 95, 21] and desire to sort it in increasing order, so that 12 becomes the first element and 95 becomes the last element. In other words, the array should become [12, 21, 35, 67, 95].
Quicksort begins by identifying a “pivot” which is one of the elements in the given array. There are many pivot selection strategies but for simplicity we will assume that the first element is the pivot. Then quicksort does a series of swaps so that the pivot is moved to a position in the array so that everything left of the pivot is less than (or equal to) the pivot and everything right of the pivot is greater than the pivot.
For instance, given the array [35, 67, 12, 95, 21] assuming we choose 35 as the pivot, quicksort will do moves so that the array becomes [12, 21, 35, 95, 67]. At this point, now that 35 is in its correct position, quicksort can be called recursively on each sub-array, namely [12, 21] and [95, 67]. Each of these smaller arrays can be sorted in place and 35 will not need to move.
So how exactly do the swaps work? The following diagram illustrates how this works.
Quicksort maintains, in addition to the pivot, two sets of pointers, symbolized as left (l) and right (r) initialized to the leftmost and rightmost locations of the array. The left pointer is moved (right) till it reaches an element higher than the pivot. Similarly, the right pointer is moved (left) till it reaches an element less than the pivot. Note that for the above example, the left pointer is moved to point to 67 and the right pointer stays at 21. At this point a swap happens and the array becomes [35, 21, 12, 95, 67].
The pointers continue to move until the same condition is met. This time, the right pointer points to 12 and the left pointer points to 95. Note that the pointers have crossed each other. When this happens the pivot is exchanged with the right pointer, yielding the array [12, 21, 35, 95, 67].
35 reaches its intended destination. Quicksort is now recursively called with [12, 21] and with [95, 67] and the results of these sorts and returned to yield the final sorted array, namely [12, 21, 35, 67, 95].
How efficient is quicksort?
Note that quicksort sorts elements in place - like bubble sort, it just swaps elements but unlike bubble sort it is more efficient. Its average-case performance is O(n*log(n)) where n is the size of the array.
What are the advantages of quicksort?
Quicksort is a divide-and-conquer algorithm like mergesort and thus can be defined recursively. Because it sorts in-place, its memory requirements are not as high as that of mergesort. Also, compared to insertion sort and bubble sort, its time complexity is very competitive. Finally, even though the time complexity of O(n*log(n)) is comparable to that of merge sort, the constant factor hiding in the big O() notation is smaller in the case of quicksort.
What are the disadvantages of quicksort?
Quicksort’s worst-case complexity can be O(n^2). It is not a stable sorting algorithm meaning it does not retain the relative order of elements that are equal.
How can we code quicksort in Python?
We follow the worked out example shown above.
First, we write a routine that sets up the left and right pointers and moves them. The code below with comments should be self-explanatory.
def movepointers(array, left, right):
# we are setting the pivot to the leftmost element
pivot = left
while left < right:
# keep moving the left pointer to the right
# till it finds an element > pivot_value
while left < len(array) and array[left] <= array[pivot]:
left += 1
# similarly, keep moving the right pointer
# to the left
while right >= 0 and array[pivot] < array[right]:
right -= 1
# see if left and right have crossed each other
# if not, we can simply swap them
if (left < right):
array[left], array[right] = array[right], array[left]
# at this point left and right have crossed each other
array[right], array[pivot] = array[pivot], array[right]
return(right)
Next, we setup a function to find the partition point and recursively call quicksort on both sides of the partition. Note that we need to pass the left and right pointer locations explicitly.
def quicksort_in_place(array, left, right):
if (left < right):
split = movepointers(array,left,right)
# at this point, split is the breakpoint
# the element at this location is in its rightful destination
# so we can call quicksort recursively leaving this element out
quicksort_in_place(array,left,split-1)
quicksort_in_place(array,split+1,right)
Finally, we have the driver function that calls quicksort automatically by setting the initial values of the left and right pointer locations.
def quicksort(array):
quicksort_in_place(array,0,len(array)-1)
return(array)Let us try to call it:
print(quicksort([35, 67, 12, 95, 21]))As expected the result is:
[12, 21, 35, 67, 95]Hope you enjoyed learning about quicksort! Learn about a different sorting algorithm in this blog post about insertion sort. Also learn about Python's enumerate() functionality. If you like the creative aspect of algorithms, you might want to checkout our blog on 5 computer science algorithms and applications. If you enjoyed the recursion in the quicksort algorithm, checkout our blogpost on the Tower of Hanoi puzzle.
Want to learn Python with us? Sign up for 1:1 or small group classes.
