This tutorial was built using Python 3.6
Quicksort is one of the most popular sorting algorithms you will come across in computer science. This is because of it’s average
case performance of O(n log n)
.
The Quicksorting algorithm uses a divide-and-conquer
approach and recursively partitions
the elements in an unsorted array around a randomly picked pivot
element.
- A Random
Pivot
element is chosen from our unsorted array. - We create 3 distinct
partitions
:- Equal - for all elements equal to our
pivot
element - Lower - for all elements lower than our
pivot
element - Higher - for all elements higher than our
pivot
element
- Equal - for all elements equal to our
- We iterate through our array and sort those that are less than our
pivot
into the lowerpartition
- We sort those that are higher than our
pivot
into the higherpartition
- We then recursively sort through these higher and lower
partitions
Whilst this typically runs with a performance of O(n log n)
, it should be noted that the worst case performance for this algorithm is actually O(N^2)
which occurs if you consistently choose the worst possible point in the array to pivot
on.
Implementing this in Python
Now that we understand the logic behind the quicksorting algorithm, it’s time to implement this in Python. Below we’ll be defining a quicksort()
function which will take in an array
as it’s only parameter.
|
|
Testing it works
We can test this by doing the following:
|
|
Conclusion
If you found this tutorial useful or require further assistance or info then please let me know in the comments section below!