QuickSort!
Hello Everyone,
Today I will be talking about a sorting algorithm called QuickSort. QuickSort is pretty complex but that does not mean it’s not doable. So Quicksort uses a technique called pivoting, to break a list into a smaller list and the smaller list uses pivoting technique and so on until it's sorted
The array above starts with 3,7,8,5,2,1,9,5,4 we first pick a random pivot. In this example, 4 is going to be our pivot. Once we pick this pivot, we want all numbers that are less than 4 on the left side and all the numbers greater than 4 on the right side.
Then we start comparing the numbers 3 < 4 and it’s to the left of 4 so it’s fine.
7 is greater than 4, so we move 4 to the left position to make space for 7. 7 jumps over to the right and we swap the 5 that 4 came into 7 position.
Now we check 5 and 4, so we move 5 to the right of 4 and swap 9
Once again 9 is great than 4 so 9 comes to the right of 4.
8 is greater than 4, so we move 8 on the right
Finally, 5 is greater than 4, so 4 and five switch places.
Now we know that everything on the left of 4 is less than and everything on the right side is greater than 4 however it’s not sorted. From there we use divide and conquer to split the list. and we do the same thing we did above.
We get a pivot on the left list 2, we say everything on the left of 2 is less than 2 and right greater, and we get everything sorted.
We get a pivot on the right list 7, and we do the same thing until we split the list with 7 in the middle. We keep breaking down the list until its sorted. After the right side is sorted we combine it with the left and we have the list fully sorted.
Implementation in JavaScript
function pivot(arr, start = 0, end = 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 pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// Swap the pivot from the start the swapPoint
swap(arr, start, swapIdx);
return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length -1){
if(left < right){
let pivotIndex = pivot(arr, left, right) //3
//left
quickSort(arr,left,pivotIndex-1);
//right
quickSort(arr,pivotIndex+1,right);
}
return arr;
}There you have it. I hope you found this blog helpful. If you’re having any difficulty or need more explanation, I’m more than happy to help you. Please connect with me on LinkedIn or my email is singhamritpal49@gmail.com. Also, check out my blog on Merge Sort.
Happy Coding :)
