![](https://hackernoon.com/hn-images/1*QAoyEDNF_3p_2LCUgW-O1Q.png)

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](https://www.pyler.io/books).

![](https://hackernoon.com/hn-images/1*vjvHjryTsqnYojTTDByuIg.png)

Slither into Python available to pre-order for 66% off.

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

Algorithms Explained: Quicksort

Too Long; Didn't Read

@pylearn.live

RELATED STORIES