Quicksort Algorithm
Imagine you have a task of arranging a team by height from the shortest to tallest. Initially, we ask them to get in line, which they do, in whatever order they want. We start solving this problem by picking a person at random from the group or perhaps selecting the first or the last person. It doesn’t really matter. We just need to pick somebody.
We then tell the teammates to move around so that all individuals who are shorter than the chosen one should move to the left of them, and all the rest should move to their right. Note that we did not ask the team to put themselves in the right order. We only asked them to move relative to the person we chose. So they formed two groups, on the left and right of the chosen one. The individuals in these groups are not in any shorter-to-taller sequence. We do know, however, that one person is certainly in the final position in the line we are trying to form: the very person we initially picked. All the teammates on the left are shorter and all the teammates on the right are at least as tall. We call the person we picked pivot because the rest of the people have moved around them.
Now we shift our attention to one of the two groups, left or right — say the left. Again we pick a pivot in that group at random. We ask the teammates in that group to do the same thing as before: move so that if they are shorter, they move to the left of the pivot and otherwise they should end to the right. We will have again two new, smaller groups. We keep dividing the group around a new pivot and repeat partitioning.
If we have a group of numbers that we can sort, we can follow a similar process, picking up a number at random and moving around the rest of the numbers so that those that are smaller end up before our chosen number, and the rest end up after it. We’ll repeat the process in the smaller groups that are formed; in the end, we’ll have all the numbers in the right order. This is the process that underlies the quicksort algorithm.
Quicksort is a sorting algorithm that repeatedly partitions the input into low and high parts (each part unsorted), and then recursively sorts each of those parts. To partition the input, quicksort chooses a pivot to divide the data into low and high parts. The pivot can be any value within the array being sorted, commonly the value of the middle of the last array element. For example, for the list [4, 34, 10, 25, 1], the middle element is located at index 2 (the middle of indices [0, 4]) and has a value of 10.
Once the pivot is chosen, the quicksort algorithm divides the array into two parts, referred to as the low partition and the high partition. All values in the low partition are less than or equal to the pivot value. All values in the high partition are greater than or equal to the pivot value. The values in each partition are not necessarily sorted. Ex: Partitioning (4, 34, 10, 25, 1) with a pivot value of 10 results in a low partition of (4, 10, 1) and a high partition of (34, 25). Values equal to the pivot may appear in either or both of the partitions.
Quicksort involves fewer comparisons and swaps than other algorithms, so it’s able to sort quickly in many cases. We choose a single pivot element from the list. Every other element is compared with the pivot, which partitions the array into three groups:
- A sub-array of elements smaller than the pivot.
- The pivot itself.
- A sub-array of elements greater than the pivot.
Let’s look at another example given the array [6, 5, 2, 1, 9, 3, 8, 7].
If we chose 6 as a pivot:
[5, 2, 1, 3] sub-array elements are lesser than 6
[9, 8, 7] ] sub-array elements are greater than 6
[5,2,1,3] will never be compared with [9,8,7]
Let’s explore the steps of the quicksort algorithm further.
We have another array to sort:
To solve the sorting problem, I’ll write a function called quick_sort and this function expects to be passed some array, a star index, and an end index.
The first time I call quick_sort, I am going to say sort the array from 0 to 4.
Because this algorithm will be implemented using recursion, one thing I want to check is if start is before end. We are going to recursively subdivide the array and at some point when start and end are in the same spot, that’s when we are done and return the result.
So the first thing we check is:
If (start >= end) return; that’s going to get us out of the recursive function.
As we discussed earlier, the idea of the quicksort is picking a pivot. It could be the start, end of the array, or a random index. For this example, we are going to pick the end spot as our pivot.
Now, I want to take everything that is less than the pivot and put it on one side of the array, and everything that is greater than the pivot I put on the other side of the array.
This is what the first partitioning looks like in our case:
Number 2 is less than 4 (our pivot) and is placed to the left of the pivot and numbers 7, 5, and 6 are each greater than the pivot and are placed to the right of the pivot. The numbers in the sub-arrays don’t have to be sorted.
Our partition function will receive 3 parameters — the array to be sorted, start index, and end index.
partition(arr, start, end)
We want the partition function to return an index value of where the pivot ended up.
idx = partition(arr, start, end)
So in the first iteration, the partition function returns index 1. This is where our pivot ends up after we compare all the values to it and position numbers to the right and left of the pivot based on the condition of values being less than or greater than the pivot value.
Now that we got the index of where the pivot is, we are going to recursively call quick_sort on our array from start to that pivot index and from the pivot index + 1 to the end of the array.
quick_sort(arr, start, idx — 1)
quick_sort(arr, idx + 1, end)
So let’s recap our steps:
- We start with our array and pick an arbitrary pivot
- We put everything on one side or the other (the right or left side of the pivot based on the lesser or greater value than the pivot).
- We store the index of where the pivot ends up in a variable (after the reordering of the numbers in relation to the pivot)
- Then we quicksort both sides — numbers to the left of the pivot and numbers to the right of the pivot.
Let’s now implement the quicksort algorithm in Python.
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
return i + 1
def quick_sort(array, low, high):
if low < high:
pidx = partition(array, low, high)
quick_sort(array, low, pidx - 1)
quick_sort(array, pidx + 1, high)
arr = [7, 2, 6, 5, 4]
quick_sort(arr, 0, len(arr) - 1)Although the worst-case time complexity of Quicksort is O(n^2), the average time complexity of this algorithm is O(n log n). Quicksort achieves optimal performance if we always divide the arrays and subarrays into two partitions of equal size. Quicksort is faster in practice because its inner loop can be efficiently implemented in different ways by changing the choice of the pivot so that the worst case rarely occurs for a given type of data.
Explore other common sorting algorithms:
