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; } 
Top comments (0)