So in my endeavour to learn some sorting algorithms I have decided to look at implementing the Quicksort algorithm. This is has been significantly harder than implementing a Selection Sort which you can read about in my previous post 'Selection Sort with Python'. Part of the reason it has been hard is because I attempted to do this without properly reading and understanding the algorithm but also because it is a bit more complicated than a Selection Sort!
However, I eventually got the algorithm working and I have had a lot of fun exploring this sorting method! My Saturday afternoon frustration can be thought of as an 'Ode to Reading the Instruction Manual'.
The algorithm works by dividing the list to be sorted around a pivot or partition point into sub-lists of elements based on whether they are greater than or less than the partition. The process is then repeated with the resultant lists decreasing in length until each sub-list is ordered from lowest to highest. The sub-lists are then combined to give the user back the sorted list. It is an $\mathcal{O}(N\log N)$ process which, as I will demonstrate at the end of this article, is quicker than an $\mathcal{O}(N^2)$ process like the Selection Sort.
This idea of sub-list splitting is what initially caused me some confusion and I want to try and explain why so that you don't encounter the same problems. The splitting into sub-lists is what the algorithm is fundamentally doing but there is perhaps an easier way to think about it.
In my first attempt at implementation I tried to physically define the sub-lists as list A and list B each time I split a list up to create a tree like structure with different levels. This is shown in the figure below which has been adapted from a figure in this Geeks for Geeks article. The top level is the original unsorted list and the subsequent branches are the sub-lists after splitting around the partition point shown in ( ). The left hand branches at each division are the elements of the list that are smaller than the partition value.
Splitting, tracking and putting back together sub-lists isn't a particularly easy to implement the algorithm. Rather than splitting the original list into two separate sub-lists what we actually want to do is to redefine the original list around each partition. It then seems clearer to write the second level, after a single partition of the original list, as a single list of the same length as our original list,
$10, 30, 40, 50 ( 70 ) 90, 80$.
where I have highlighted the partition again using parenthesis. If the indexing of our unsorted list starts from 0 then the 2nd element has been redefined from '80' to '30' after the first partition and so on. Note also that the element we used as our pivot is now in the correct place for our sorted list.
I have italicised the word 'redefine' because this is where the distinction between my first attempt and the easier implementation comes in. There are no additional lists to keep track of and at each level in the sorting we simply have a new semi-sorted list. The third level in the above diagram would then correspond to,
$10, 30, 40 ( 50 ) ( 70 ) ( 80 ) 90$
and the algorithm continues recursively redefining the elements in our list until the list is sorted. We only need to track one list and exercise some caution in how we are redefining the elements at each step.
So how do we do this in Python? Well we can write the algorithm more concisely as,
- Identify a pivot or partition point in the unsorted list. This pivot point can be arbitrarily chosen as, for example, the central index or the last index as long as it's choice is kept consistent as the algorithm progresses.
- Redefine the elements of the list so that the pivot point is in it's correct position, the elements to it's left are less than the pivot and the elements to it's right are greater in value.
- Repeat the process until the list is sorted.
From the description above we essentially need two functions. One to define the partitioning and to redefine the list and another function that acts as a recursive call to the partitioning.
We will begin with the partitioning function which is given by,
def partition(list, low, high):
pivot = list[high]
i = low
for j in range(low, high):
if list[j] < pivot:
list[i], list[j] = list[j], list[i]
i += 1
list[i], list[high] = list[high], list[i]
print(low, high)
return i
Here 'low' and 'high' refer to the first and final indices of the sub-list to be reordered. For example, when the function is first called we are inputting the unsorted list with 'low' = 0 and 'high' = len(unsorted list) - 1. The pivot is defined as the last element in the list, as in the diagram above, and we iterate through the sub-list from index 'low' to 'high' swapping elements as we go. Elements that have values less than the pivot are swapped with the element given by index 'low' which is then incremented upwards through the list. All elements that have values higher than the pivot value are essentially left where they are and finally the pivot value 'list[high]' is placed into it's correct position given by index 'i' after the for loop. Index 'i' becomes the new dividing line or partition index between the subsequent sub-lists at the next level in the tree diagram.To repeat this process we can define the following function,
def quicksort(list, low, high):
if low < high:
p = partition(list, low, high)
quicksort(list, low, p - 1)
quicksort(list, p + 1, high)
sorted_list = list
return sorted_list
Here if 'low' is less than 'high' or in other words the sub-list length is greater than 1 then the sub-list is partitioned and the function is called again for the two new sub-lists defined from 'low' to 'p-1' and 'p+1' to 'high'. When all of the sub-lists have length 1 then the list is sorted and the result output as 'sorted_list'. Calling this function will therefore perform the sorting process.To stress the point, note that there is no definitions of new sub-lists as the algorithm progresses and that we are simply redefining the elements in the original lists around the partitions. This is really important for implementing the algorithm well!
As in my previous article on the Selection Sort I have wrapped these functions into a Python Class and you can find this on my github via the link at the end of the article.
We can illustrate what is happening as the algorithm progresses via the figure below where the partition or pivot is plotted in red after sorting of it's associated sub-list. The data set is 200 random uniformly distributed numbers between 0 and 100.
To further illustrate this algorithm in action we can include vertical lines showing the limits of each sub-list and this is shown below. In each frame the vertical lines show the upper and lower limits on a single sub-list and the data between the limits has been reordered with the partition in it's correct, sorted position. The lists defined either sides of the partition and up to the limits are then progressively sorted in the following iterations of the algorithm.
So now we have seen the algorithm in action and illustrated that the code above works we can look at how the sorting time scales with the number of data points $N$ and compare this to the results for the Selection Sort. At the beginning of the article it was stated that a Quicksort is approximately $\mathcal{O}(N\log(N))$ process which means that the time taken to complete a sort scales with $N\log(N)$. As $N$ becomes large this becomes a much quicker method than the Selection Sort which scales as $N^2$. This is illustrated in the figure below. For each value of $N$ the data sets are random uniform numbers between 0 and 100.
The increased speed of the Quicksort over algorithms like the Selection Sort makes it a commonly implemented algorithm. The code for this project can be found on my github here.
I hope that this article has been clear and that you have as much fun implementing this as I have! Comments are always welcome!
Thanks for reading!!
More interesting articles:
Comments
Post a Comment