Sorting Algorithms: Quick Sort
Let’s Sort! In this series, I’ll be covering sorting algorithms. Most programming languages will come with a built-in sort function but in order to write better code, you need to know what’s going on in the background. If you are preparing for software engineering interviews, it’s very likely that one or more sorting algorithms may come up during your interviews. The sorting algorithms I’ll be covering in this series are:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Radix/Bucket Sort
- Heap Sort
What is Quick Sort?
Quick Sort is a very fast algorithm used to sort lists of values. It is not the easiest algorithm to understand or implement but we are going to dive into it today, break it apart and learn how it works!
How Does it Work?
In Quick Sort, you have an array of values and one value is chosen as a pivot point. The pivot can be chosen at random or you can choose the first or last value in the array and set that as the pivot. Once a pivot is chosen, you iterate through the rest of the array and sort every other value in the array with respect to the pivot. Values that are smaller than the pivot are moved to the left of the pivot and values that are larger are moved to the right. Once you have completed iterating through the array and moving values as needed, the pivot will be sorted.
Once the pivot has been sorted, we look at the subarray to the left of the pivot and the subarray to the right. A new pivot is chosen for each subarray and the process repeats. This will continue to happen until the entire array is sorted.
Let’s apply Quick Sort to our example array and see how it works:
We start by picking a pivot. To keep things simple, we are going to pick the first value in the array as our pivot. In this case our pivot = 6 (In blue below). We are also going to set left and right pointers. The left pointer will start immediately after the pivot and right pointer will be at the end of the array.
We are going to iterate through the array until the left pointer is greater than the right pointer. At each point in our iteration, we will ask these questions:
- Is the value at the left pointer greater than the pivot?
- Is the value at the right pointer less than the pivot?
If both of these conditions are met, we swap the values at the left pointer and right pointer.
Let’s look at our values. The left pointer is pointing to 3. Is 3 greater than the pivot? No. This means that the value at the left pointer is correctly sorted with respect to the final position of the pivot. This means we should leave it as is and increment the left pointer.
The right pointer is pointing to 2. Is 2 less than the pivot? Yes it is. In this case, we keep the right pointer in the same position because 2 will need to be moved eventually.
Let’s check again. Is the value at the left pointer (9) greater than the pivot? Yes. Is the value at the right pointer (2) less than the pivot? Yes. Since both conditions have been met, let’s swap these two values. The left pointer will then increment and the right pointer will decrement:
Now we have left = 8 and right = 5. Is the left pointer pointing to a value greater than the pivot? Yes. Is the right pointer pointing to a value smaller than the pivot? Yes. Let’s swap again:
Left = 4 and right = 6. Is the left pointer pointing to a value greater than the pivot? No. Is the value at the right pointer less than the pivot? Also no. Let’s continue to move our pointers.
Our left pointer is now greater than the right pointer. Once this has happened, we swap the value at the pivot with whatever the value is at the right pointer. Why? Because we know that whatever is at the right pointer will always be smaller than the pivot.
6 (In green) is in its final sorted position. We now have to apply quick sort to everything to its left (index 0–3) and everything to its right (index 5–7).
We start with the smaller subarray. In this case it is the right subarray from index 5 to 7.
Let’s set the pivot to the first value in the subarray, set the left pointer to value next to the pivot and set the right pointer to the last value in the subarray:
We now compare: Is the value at the left pointer greater than the pivot? Yes. Is the value at the right pointer less than the pivot? No. Our left pointer will stay in its place and our right pointer will decrement:
Both the left and the right pointer point to the same value. Is the left pointer greater than the pivot? Yes. Is the right pointer less than the pivot? No. Let’s move the right pivot:
Now that the left pointer is greater than the right, we should swap the pivot value with whatever is at the right pointer. In this case, the right pointer is at the pivot itself so we do not need to swap anything. We have completed Quick Sort for this half of the array.
Let’s turn our attention to the left half now and set up our new pivot and our pointers:
Is the value at the left pointer greater than the pivot? No. Is the value at the right pointer less than the pivot? Also no. Let’s move both pointers:
Is the value at the left pointer greater than the pivot? No. Is the value at the right pointer less than the pivot? Yes. Let’s move the left pointer forward and leave the right as is:
Now that our left pointer is greater than the right, we swap the pivot with whatever is at the right pointer:
We’re almost there! Now let’s apply Quick Sort to what is to the left of our newly placed pivot (index 0–1) and what is to the right of our pivot (index 3).
We start with the smaller subarray (the right one). Since this subarray is of length 1, we consider it to be sorted. Let’s then move on to the left:
Is the left pointer’s value greater than the pivot? Yes. Is the right pointer’s value less than the pivot? No. Let’s decrement our right pointer and leave our left in place:
Since our left pointer is greater than our right, we want to swap the pivot with whatever value is at the right pointer. In this case it’s the pivot itself so the pivot has been sorted. We now only have a subarray of length one to the right of our pivot. Since it’s length is one, we consider it to be sorted. Therefore our full array has now been sorted!
Time and Space Complexity
What is the worst case for Quick Sort? If your starting pivot is the greatest value in the array, you will move it to a point where every other value is to its left and it alone is on the right. You will not have broken down your problem into half, you would have actually just gotten rid of one value to sort and now you have n-1 values to sort again. If you run into this problem again and again where your new pivot is also greater than every other value, your worst run time will be O(n²).
So why is Quick Sort considered to be a fast algorithm? Although we have a poor worst case time complexity, the average case is that our algorithm will run in O(nlog(n)). This is because after every pivot is sorted, we split our problem in half and then work on those halves until everything is sorted. Because we are halving our problem each time and we are iterating through all the values, the average time complexity is O(nlog(n)).
The Space Complexity will be O(log(n)). In order to implement Quick Sort, we use recursion to reapply it each time to the subarrays we produce when moving the pivot. With every recursive call, we need to add those as frames onto our call stack. The space we take on the call stack will be O(log(n)).
Note: we always start the recursive call with the smaller subarray to minimize space taken on the call stack at a time.
Code Implementation
Let’s look at Quick Sort in Python:
We’re going to implement Quick Sort using Recursion. We will use a helper function that will take in a few extra parameters. Specifically, we need to input a start index and an end index for whatever subarray we are working on. In our main quickSort function, we call our quickSortHelper function and use the full array by passing in 0 as the start index and len(array) — 1 as the end index. Lastly, we return the array because we assume that our helper method will have sorted the array for us:
def quickSort(array):
quickSortHelper(array, 0, len(array) - 1)
return arraydef quickSortHelper(array, start, end):
So as with any recursive function, we need to define a base case. In Quick Sort, the base case is that the start index is greater than or equal to the end index. This means that we are dealing with an array of length 1 or 0.
def quickSortHelper(array, start, end):
if start >= end:
returnIf we are not at the base case, we need to define our pivot. As mentioned before, we are going to choose the first index in the array as our pivot. If you want to implement Quick Sort by defining a random pivot, you can add a few lines or create another helper function that will pick a random index and then swap its value with whatever is at the first index of the array in order to then iterate through the rest of the array to compare values.
For simplicity sake, we will stick with picking the first value as the pivot. We set our left pointer to start + 1 and our right pointer to end:
def quickSortHelper(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = endNow we need to iterate through the rest of the array until left is greater or equal to right. If our two conditions of the left value being greater than the pivot and the right value being less than the pivot are met, we swap.
def quickSortHelper(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left < right:
if array[left] > array[pivot] and array[right] < array[pivot]:
array[left], array[right] = array[right], array[left]
if array[left] <= array[pivot]:
left += 1
if array[right] >= array[pivot]:
right -= 1Once our while loop is complete, we can swap the value at the right index with the value at the pivot:
def quickSortHelper(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left < right:
if array[left] > array[pivot] and array[right] < array[pivot]:
array[left], array[right] = array[right], array[left]
if array[left] <= array[pivot]:
left += 1
if array[right] >= array[pivot]:
right -= 1
array[pivot], array[right] = array[right], array[pivot]Now that our pivot is sorted, we want to sort everything to its left and everything to its right. First we have to figure out which subarray is the smaller subarray so that we can call our helper function on it first to save space on the call stack. The left subarray is smaller than the right subarray if the length from the start to right-1 (because the pivot will end up placed where the right pointer lands at the end of the iteration) is less than the length from right+1 to the end.
def quickSortHelper(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left < right:
if array[left] > array[pivot] and array[right] < array[pivot]:
array[left], array[right] = array[right], array[left]
if array[left] <= array[pivot]:
left += 1
if array[right] >= array[pivot]:
right -= 1
array[pivot], array[right] = array[right], array[pivot] smallerLeftSubarray = right - 1 - start < end - (right + 1) if smallerLeftSubaray:
quickSortHelper(array, start, right - 1)
quickSortHelper(array, right + 1, end)
else:
quickSortHelper(array, right + 1, end)
quickSortHelper(array, start, right - 1)
And that’s it :) This is Quick Sort. It’s a very useful algorithm to sort values in an efficient way. The best case/average case time complexity is O(nlog(n)) and the space complexity is O(log(n)).
Thank you for reading!
