## DEV Community

Dumb Down Demistifying Dev

Posted on • Updated on

# Quick Sort

What do we understand about Quick Sort?

• Usually implemented recursively
• Mutates the original Array
• Similar mental model to reversing a Binary Tree
• Similar to Merge Sort
• It is a Divide & Conquer algorithm
• It comprises of 2 functions
• Main function recursively splits the Array into left and right halves
• Left and right half is determined via Array index
• 2nd helper function does the swap and returns the new pivot index
• by convention, last value is the pivot value to be compared with
• if current loop index's value is less than pivot value
• increment
• smaller to the left of the pivot
• bigger to the right of the pivot
• lastly, return the pivot point
• Best video explanation I found online:
• Time Complexity:
• Best : O(nlogn)
• Average: O(nlogn)
• Worst : O(n^2)
• Space Complexity:
• O(logn)
``````// 27, 18, 6, 21, 26, 24
// |
// i
// |
// pivotIndex
//                    |
//                    pivotValue

function getPivotPoint(arr, start, end) {
// by convention we always pick the last element as pivot
let pivotValue = arr[end];
// pivot index should at the end hold the larger value compared to pivot
let pivotIndex = start;

for (let i = start; i < end; i++) {
// as loing as values on the left of the pivot is smaller in value,
// we swap the index with the latest updated pivot index
if (arr[i] < pivotValue) {
if (i !== pivotIndex) {
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
}
pivotIndex++;
}
}

// swap the latest updated pivot index with the pivot value itself
// everything on the right is now larger value than the pivot value
[arr[end], arr[pivotIndex]] = [arr[pivotIndex], arr[end]];

// return new pivot point
return pivotIndex;
}
function QuickSort(arr, start = 0, end = arr.length - 1) {
// base case
if (end > start) {
const pivot = getPivotPoint(arr, start, end);
QuickSort(arr, start, pivot - 1);   // do the pivot swap on the left
QuickSort(arr, pivot + 1, end);     // do the pivot swap on the right
}
return arr;
}
``````