Algorithms Explained: Quicksort
Today we’ll look at a very important sorting algorithm: quicksort. Quicksort is a recursive sorting algorithm that employs a divide-and-conquer strategy.
I wont be explaining how recursion works as I’ve already wrote an article about that here.
Since this is a divide-and-conquer algorithm we want to take a list of unsorted integers and split the problem down into two easier problems and then break each of those down…. and so on.
To achieve this I’ll first cover quicksorts core operation: partitioning. It works as follows:
>>> A = [6, 3, 17, 11, 4, 44, 76, 23, 12, 30]>>> partition(A, 0, len(A)-1)>>> print(A)[6, 3, 17, 11, 4, 23, 12, 30, 76, 44]
So what happened here and how does it work? We need to pick some number as our pivot. Our partition function takes 3 arguments, the list, the first element in the list, and the pivot. What we are trying to achieve here is that when we partition the list, everything to the left of the pivot is less than the pivot and everything to the right is greater than the pivot. For the first partition seen above, 30 is our pivot. After the partition we see some elements have changed position but everything to the left of 30 is less than it and everything to the right is greater than it.
So what does that mean for us? Well it means that 30 is now in its correct position in the list AND we now have two easier lists to sort. All of this is done in-place so we are not creating new lists.
Lets look at the code:
def partition(A, p, r):
q = j = p
while j < r:if A[j] <= A[r]:A[q], A[j] = A[j], A[q]q += 1
j += 1
A[q], A[r] = A[r], A[q]
return q
The return q at the end isn’t necessary for our partition but it is essential for sorting the entire list. The above code works its way across the list A and maintains indices p, q, j, r.
p is fixed and is the first element in the list. r is the pivot and is the last element in the list. Elements in the range A[p:q-1] are known to be less than or equal to the pivot and everything from A[q-1:r-1] are greater than the pivot. The only indices that change are q and j. At each step we compare A[j] with A[r]. If it is greater than the pivot it is in the correct position so we increment j and move to the next element. If A[j] is less than A[r] we swap A[q] with A[j]. After this swap, we increment q, thus extending the range of elements known to be less than or equal to the pivot. We also increment j to move to the next element to be processed.
Now onto the quicksort part. Remember it is a recursive algorithm so it will continuously call on partition() until there is nothing left to partition.
Lets look at the code:
def quicksort(A, p, r):
if r <= p:return
q = partition(A, p, r)quicksort(A, p, q-1)quicksort(A, q+1, r)
return A
Its that simple. All we do here is check if the index of the pivot, is less than or equal to the index of the start of our list we want to partition. If it is we return as whatever list was passed does not need to be partitioned any further.
Otherwise, we partition the list A, and call quicksort again on the two new sub lists.
Quicksort works best on large lists that are completely scrambled. It has really bad performance on lists that are almost sorted. Or in Big-O notation, the best case (scrambled) is O(n log(n)) and in the worst case, (almost or completely ordered list) is O( n^2).
This topic is covered in further detail in our new book “Slither into Python” which you can now pre-order for just €5.99 — Our introduction to the Python programming language for beginners book, designed to take you from a complete beginner to a competent and skilled programmer in just 22 chapters, covering a whole range of topics. Check it out HERE.
Slither into Python available to pre-order for 66% off.