I am currently using Algomonster as my guide for learning and improving algorithms and data structures. The first section I needed to conquer was sorting algorithms. Merge sort and quick sort were a bit complicated but I was able to understand them thanks to this video on FreeCodeCamp. While implementing merge sort was fairly straightforward once you understand recursion, I struggled to understand the implementation for quicksort. If you are like me then I hope that this blog post helps you to be able to implement it with confidence.
What is Quick Sort?
Quick sort uses the divide and conquer method to sort all items. As a result of which, it has better time complexity compared to the basic sorting algorithms like the selection sort, insertion sort, and bubble sort. But it has a worst case time complexity of O(n^2) just like the basic sorting algorithms unlike merge sort that has a stable time complexity of O(n log(n)).
Both merge sort and quick sort use the divide and conquer method to sort. But why was I having trouble understanding the quick sort implementation? Because the implementation uses in-place sorting. Why? So that we don’t use extra space when running the algorithm. This makes quick sort better than merge sort in terms of space complexity, O(log (n)) vs O(n).
Understanding the implementation step-by-step
I am going to share the whole solution first and then break it apart into pieces. The solution is in JavaScript(JS) but it can be interpreted in other languages as it does not use any function-specific methods.
Full Solution
const numbers = [108, 76, 8, 2, 11, 5, 54, 99, 300, 1, 0];
function quickSort(array, left, right){
let pivot;
let partitionIndex;
if(left < right) {
pivot = right;
partitionIndex = partition(array, pivot, left);
quickSort(array, left, partitionIndex - 1)
quickSort(array, partitionIndex + 1, right)
}
return array;
}
function partition(array, pivot, startingIndex) {
let partitionIndex = startingIndex;
let pivotValue = array[pivot];
for(let i = startingIndex; i < pivot; i++) {
if(array[i] < pivotValue) {
swap(array, i, partitionIndex);
partitionIndex++;
}
}
swap(array, partitionIndex, pivot);
return partitionIndex;
}
function swap(array, firstIndex, secondIndex) {
let temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);
Step 1
Create the parent function that takes in an array, the first index and the last index of the array section to be sorted. Within the function, declare variables for pivot and partition index.
function quickSort(array, left, right){
let pivot;
let partitionIndex;
}
Pivot is used as the main point with which we divide or partition our array. The last element in the array is normally used as a pivot but it could be any of the items in the array.
The partition index here is used to keep track of the position of the pivot item in the array as it undergoes partition.
Step 2
Next, we'll be adding the condition that houses our recursive calls to sort the array. We should continue with the sort only as long as the left index is lesser than the right index. If this condition is not met, it means that the array has been sorted and we return the sorted array.
if(left < right) {
}
return array;
Now, let's examine the block of code in the conditional statement. If the left index is less than the right index passed into the quickSort function, we assign the pivot variable with the right index which is the last index of the array partition of that function call. In the first iteration, the array is not partitioned yet, so the pivot is the index of the last item from the original array.
Within the conditional statement, we assign a function call that returns the updated position of the pivot to partitionIndex. This function takes in the array, the current index of the pivot, and the starting position of the array section to be partitioned.
partitionIndex = partition(array, pivot, left)
We then proceed to call the quickSort function recursively. Once, for the section of the partition containing items smaller than the pivot value and once for the partition section with items larger than the pivot value.
Showing the full quickSort function👇
function quickSort(array, left, right){
let pivot;
let partitionIndex;
if(left < right) {
pivot = right;
partitionIndex = partition(array, pivot, left)
quickSort(array, left, partitionIndex - 1)
quickSort(array, partitionIndex + 1, right)
}
return array;
}
Step 3
Let us now look at the helper functions. In the helper function for partition, we declare another variable called partitionIndex and assign the starting index to it. We then loop through the array subset starting from the startingIndex to the pivot.
function partition(array, pivot, startingIndex) {
let partitionIndex = startingIndex;
let pivotValue = array[pivot];
for(let i = startingIndex; i < pivot; i++) {
if(array[i] < pivotValue) {
swap(array, i, partitionIndex);
partitionIndex++;
}
}
swap(array, partitionIndex, pivot);
return partitionIndex;
}
For every loop, we check whether the current item in the loop is less than the item at the pivot which is defined as the pivotValue. If the condition is met we swap the value at the current position with the value at the partitionIndex and increment the partitionIndex by 1. This way, we'll have all the items smaller than the pivot value stacked at the beginning followed by the items larger than the pivot value.
for(let i = startingIndex; i < pivot; i++) {
if(array[i] < pivotValue) {
swap(array, i, partitionIndex);
partitionIndex++;
}
}
After the loop is done swap the value at the partitionIndex with the pivot value to update the pivot position so that the smaller items are on the left and the larger items are on the right of the pivot. Finally, we return the updated pivot position.
swap(array, partitionIndex, pivot);
return partitionIndex;
The final helper function is the swap. It contains the logic for swapping items in an array.
function swap(array, firstIndex, secondIndex) {
let temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
That's it! Do let me know in the comments if there is a mistake or if this helped you in any way. Thanks for reading!
