Quicksort is one of the most popular algorithms to sort with. It’s average use case is great, it’s relatively easy to implement, and it’s worst case isn’t that easy to stumble into. We’ll go over how it’s actually implemented and what can be done better with it.
Introducing Quicksort
Quicksort is a divide and conquer algorithm. It works by splitting the data set into increasingly smaller sets and recursively iterating over them until there’s nothing left. It tends towards O( n log n ) but can be O( n2 ) in the worst scenarios.
Quicksort uses this basic process in order to sort:
1. Pick a pivot
2. Partition the array into 3 subarrays: A. items < pivot, B. the pivot, C. items >= pivot
3. Recursively quicksort A and C
Picking a Pivot
For the sake of simplicity, most implementation examples just use the leftmost or rightmost element. This obviously isn’t always efficient or desirable, but is easy as a good jumping off point. Many implementations use a random pivot somewhere in the array. We won’t really get into the pros and cons of our initial pivot at this point.
Partitioning the Array
Next, we need to partition the array. This means that we take our pivot point and move everything smaller to the left, and everything bigger or equal to the right. We’ll get into the code in a little bit.
Recursively Quicksort
We then continue this process on each sub-array. We run our quicksort recursively as follows:
quicksort( array, l, p - 1 )
quicksort( array, p + 1, r )l is our left element. p is our pivot. r is our right element. array is our array to be sorted. We run our quicksort on the left side of the pivot, then again on the right side.
A Note About Quicksort
Most implementations of quicksort will sort in place. This means that there is no merge step or similar like some sort algorithms use. This also means that the original array will be changed. You can avoid this by doing a deep copy into another same data structure if you need to keep the original data.
Quicksort in Code (Lua)
Let’s look at a basic implementation of quicksort in Lua:
function quicksort( array, l, r )
l = l or 1 --Lua arrays start with an index of 1; so we set this to "l" or else 1
r = r or #array --set this to "r" or else the max size of "array"
if l < r then
local p = partition( array, l, r )
quicksort( array, l, p - 1 )
quicksort( array, p + 1, r )
end
end
function partition( array, l, r )
local q = array[ r ]
local i = l - 1
for j = l, r - 1 do
if q >= array[ j ] then
i = i + 1
array[ i ], array[ j ] = array[ j ], array[ i ]
end
end
array[ i + 1 ], array[ r ] = array[ r ], array[ i + 1 ]
return i + 1
endWe call our function as follows:
local mess = { 1, 2, 6, 5, 4, 10, 42, 1, 2, 1 }
quicksort( mess, 1, #mess )Breaking Down quicksort
Let’s break down the first section of code for our actual quicksort function:
function quicksort( array, l, r )
l = l or 1 --Lua arrays start with an index of 1; so we set this to "l" or else 1
r = r or #array --set this to "r" or else the max size of "array"
if l < r then
local p = partition( array, l, r )
quicksort( array, l, p - 1 )
quicksort( array, p + 1, r )
end
endWe define our function and then set some sane limits to our l and r variables. We want the l to either be defined, or set to the base index (1 in Lua) for our array. r is set to whatever is passed, or the maximum index for array. Since this is a recursive function, we need to have some kind of limitation. We only run our algorithm if l is less than r. This prevents our pivot item p from ever pushing us to where we’re in an infinite loop. We define our pivot item p off of our partition function and then quicksort each side of our array.
Breaking Down partition
Let’s break down the code for partition:
function partition( array, l, r )
local q = array[ r ]
local i = l - 1
for j = l, r - 1 do
if q >= array[ j ] then
i = i + 1
array[ i ], array[ j ] = array[ j ], array[ i ]
end
end
array[ i + 1 ], array[ r ] = array[ r ], array[ i + 1 ]
return i + 1
endWe set a variable q to our limit for our part of the quicksort. In the beginning this will be the whole array, but this will get smaller and smaller as we divide and conquer. We also set an index i which is equivalent to l – 1, or one left of our l term because we’re going to increment this counter to “follow” how many smaller elements we have.
We then perform a for loop over the range from l to r – 1. If q, which is our rightmost element in this run, is bigger or equal to the item we’re testing, the j item in the array, we increment i and swap the ith with the jth in our for loop.
At the end, we then swap our i + 1 with our rth term. If q which is our rth item in the array is the biggest, i + 1 should be equal so it will swap with itself. It’s computationally cheaper than writing in handling. Finally, we return i + 1 because that should be the pivot of this iteration. Every previous element has been moved to the left if it was smaller.
If you get it, you can stop reading. The next part is going to cover a verbose breakdown of a runthrough of quicksort. We’re going to iterate over every (relevant) step in a sort operation.
Putting It Together: A Verbose Example
Let’s take a look at a verbose output from our partition function starting with the array 3, 1, 1, 4, 2, 5, 3:
partition:
[3] [1] [1] [4] [2] [5] [3]
comparing: r = 7; i = 0
iterating from: 1 to 6
before step: [3] [1] [1] [4] [2] [5] [3]
q >= array[ j ] : 3 >= 3; iterating i from: 0 to: 1
swapping: array[ 1 ], array[ 1 ] = array[ 1 ], array[ 1 ]
3, 3 = 3, 3
after step: [3] [1] [1] [4] [2] [5] [3]
iterating from: 2 to 6
before step: [3] [1] [1] [4] [2] [5] [3]
q >= array[ j ] : 3 >= 1; iterating i from: 1 to: 2
swapping: array[ 2 ], array[ 2 ] = array[ 2 ], array[ 2 ]
1, 1 = 1, 1
after step: [3] [1] [1] [4] [2] [5] [3]
iterating from: 3 to 6
before step: [3] [1] [1] [4] [2] [5] [3]
q >= array[ j ] : 3 >= 1; iterating i from: 2 to: 3
swapping: array[ 3 ], array[ 3 ] = array[ 3 ], array[ 3 ]
1, 1 = 1, 1
after step: [3] [1] [1] [4] [2] [5] [3]
iterating from: 4 to 6
before step: [3] [1] [1] [4] [2] [5] [3]
q < array[ j ] : 3 < 4; taking no action
after step: [3] [1] [1] [4] [2] [5] [3]
iterating from: 5 to 6
before step: [3] [1] [1] [4] [2] [5] [3]
q >= array[ j ] : 3 >= 2; iterating i from: 3 to: 4
swapping: array[ 4 ], array[ 5 ] = array[ 5 ], array[ 4 ]
4, 2 = 2, 4
after step: [3] [1] [1] [2] [4] [5] [3]
iterating from: 6 to 6
before step: [3] [1] [1] [2] [4] [5] [3]
q < array[ j ] : 3 < 5; taking no action
after step: [3] [1] [1] [2] [4] [5] [3]
end swapping: array[ 5 ], array[ 7 ] = array[ 7 ], array[ 5 ]
4, 3 = 3, 4
---returning: 5 as pivot---
l: 1; r: 7; q: 5
array: [3] [1] [1] [2] [3] [5] [4] We start with our array and select the rightmost element as our point of comparison, which works out to 3 in this example for our first partition. We want to basically find where 3 should finally go in the array itself. We set our increment variable i to l – 1 to start off. On our first element we see that 3 >= 3 so we increment i and swap array items indexed at i and j (which are currently the same). We could add handling for this, but it would be a waste.
We continue incrementing j and i follows it. Eventually we hit a spot where 3 < 4, so we don’t do anything this round with i. Now i is lagging behind j because there will be at least one item it swaps with at the end. We keep going and hit 3 >= 2 when j = 5 and i = 4 (on increment), so we swap our previous bigger element and the smaller element. We go and do our last comparison and find that the element is bigger so we don’t do anything.
Our i and j terms vary by 2 now, since we have 2 terms which are larger. The final step is to swap q (the item at r) and the item at i + 1 (because we include q which is our rightmost element) so that the q term will now be at its final position. Everything on the left is smaller or equal, and everything on the right is bigger.
Our partition method does virtually all of our work. Our quicksort method is just there to dispatch the partitioning. We’ve found exactly where this q term goes, so we return its index and use it as the new partition boundary for the subinstances of quicksort which do more of the same on each side. After our initial partition, we then hit the smaller items and repeat the process as follows:
quicksort( array, 1, 4 )
l: 1; r: 4
[3] [1] [1] [2] [3] [5] [4]
partition:
[3] [1] [1] [2] [3] [5] [4]
comparing: r = 4; i = 0
iterating from: 1 to 3
before step: [3] [1] [1] [2] [3] [5] [4]
q < array[ j ] : 2 < 3; taking no action
after step: [3] [1] [1] [2] [3] [5] [4]
iterating from: 2 to 3
before step: [3] [1] [1] [2] [3] [5] [4]
q >= array[ j ] : 2 >= 1; iterating i from: 0 to: 1
swapping: array[ 1 ], array[ 2 ] = array[ 2 ], array[ 1 ]
3, 1 = 1, 3
after step: [1] [3] [1] [2] [3] [5] [4]
iterating from: 3 to 3
before step: [1] [3] [1] [2] [3] [5] [4]
q >= array[ j ] : 2 >= 1; iterating i from: 1 to: 2
swapping: array[ 2 ], array[ 3 ] = array[ 3 ], array[ 2 ]
3, 1 = 1, 3
after step: [1] [1] [3] [2] [3] [5] [4]
end swapping: array[ 3 ], array[ 4 ] = array[ 4 ], array[ 3 ]
3, 2 = 2, 3
---returning: 3 as pivot---
l: 1; r: 4; q: 3
array: [1] [1] [2] [3] [3] [5] [4] We do the exact same thing with this subarray and just keep incrementing until we no more comparisons. We then do the same thing with the larger elements:
quicksort( array, 6, 7 )
l: 6; r: 7
[1] [1] [2] [3] [3] [5] [4]
partition:
[1] [1] [2] [3] [3] [5] [4]
comparing: r = 7; i = 5
iterating from: 6 to 6
before step: [1] [1] [2] [3] [3] [5] [4]
q < array[ j ] : 4 < 5; taking no action
after step: [1] [1] [2] [3] [3] [5] [4]
end swapping: array[ 6 ], array[ 7 ] = array[ 7 ], array[ 6 ]
5, 4 = 4, 5
---returning: 6 as pivot---
l: 6; r: 7; q: 6
array: [1] [1] [2] [3] [3] [4] [5] We have many other attempts to run this algorithm, but our recursion limitations prevents the endless loop and cuts off the wasted effort if it’s only a single element. At the end, our array is entirely sorted and we don’t need to merge it or do any further processing.
Featured image by Frank Magdelyns from Pixabay