Algorithms Explained: Quicksort by@pylearn.live

January 21st 2018 10,901 reads

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.

Join Hacker Noon

Create your free account to unlock your custom reading experience.