Hi there, Today is Quick Sort, one of the most talk about in sorting data structures. Quick Sort leverages on the Divide and conquer strategy by allowing elements of a list to sort themselves and checking which elements stand in front or behind. Quick Sort seems to be a little tricky, one of the fastest but definitely not the quickest as the name indicates. in this sorting Algorithm we constantly use a low/start/small , high/end/big and a pivot at any point of the list to look for a partition that holds the pivot in place as a divided list. the partition index (Pivot) will always stand at a point where values or elements after it are bigger (May not be sorted) and elements before itself being smaller (May not be sorted). if that hasn’t been done then there is no pivot yet to begin the sorting procedure. So then let’s say a Quick Sort Algorithm will need a list ie. Array, a low value and a high value. let’s take a look at how we get our pivot partition.
function PP(arr, low = 0, high = arr.length - 1) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// We are assuming the pivot
is always the first element
let i = low;
let j = high;
let pivot = arr[i];
for (let k = i + 1; k <= j; k++) {
//k can not cross j in this case
if (pivot > arr[k]) {
i++;
swap(arr, i, k);
}
}
// Swap the pivot from the low to the swapPoint
swap(arr, low, i);
return i;
}
Let’s create a function called PP for Pivot Partition where we will hold the index of the pivot value, remember the pivot has to be in such a way that all element at it’s right side(After) are greater than itself and those at the left side(Before) are lesser. our low should then be at index 0, having our high to be an infinity because the end of the list may not be known. Quick Sort uses swapping as well so you can the function ready to do it job at the right time. Assigning i and j in this case is nothing but just a way to make the algorithm much simpler. so we have i and j as our low and high. Practically our pivot is assumed to be at the beginning, remember the pivot index can be selected from the begging though the list to the end and we don’t know that for sure so we need to check every index to meet our best suited criteria to be the partition point, in fact this is one of the flows of quick sort and it plays really against it’s Big O complexities. a third variable (K) is needed to iterate though the list to catch the partition where the pivot is going to be by checking if the value of the previous pivot is greater than the current reached position. If so then swap it to make it the current pivot index. All said and done let’s now focus on the fun part, Recursion (I just love this concept 🙂 )
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
let i = PP(arr, low, high);
//low
quickSort(arr, low, i - 1);
//high
quickSort(arr, i + 1, high);
}
return arr;
}
console.log(quickSort([100, -3, 2, 50, 6, 96, 1, 2, 4, 3, 23]));
After running PP on the provided arguments for our quick sort we then recursively run the quick sort on the same sub list gotten from the Pivot Partition, eventually we get to sort our list in the expected order.
Every Quick Sort Algorithms have a best and average case time complexity of O(n*log n) which is fairly good in cases the pivot partition locates easily if not starting at the far end or from the beginning can extend the time taken to find the pivot at a far slot of the list making the worst case scenario O(n2) obviously making Quick Sort not the quickest. contrary to other sorts quick sort makes O(log n) Space complexity. If you think quick sort is too intimidating here is a simple but hacky way quick sort can still be achieved by creating two empty arrays and pushing elements into them to arrive at the result, I don’t personally recommend this but if you feel confident Go for it.
function quickSort(arr) {
if (arr.length < 2) return arr; //Base Case
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr[pivotIndex];
let less = [];
let greater = [];
for (let i = 0; i < arr.length; i++) {
if (i != pivotIndex) {
arr[i] > pivot ?
greater.push(arr[i]) :
less.push(arr[i]);
}
}
//return copies of all
return [...quickSort(less), pivot, ...quickSort(greater)];
}
console.log(quickSort([52, 69, 2, 3, 5, 23, 85, 58]));
Kindly go through to check if there could be a better way of handling this case. until then stay safe