DEV Community

Dumb Down Demistifying Dev
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;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)