Quick Sort (JS Example)

Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.

Quicksort Breakdown

Worst Complexity: n^2

Average Complexity: n*log(n)

Best Complexity: n*log(n)

Method: Partitioning

Class: Comparison Sort

Quicksort Explained

Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Quicksort Notes

Inventor: Tony Hoare

Unstable Sorting Algorithm

Quicksort has a better space complexity than merge sort

Quicksort JavaScript Implementation

/*----------------------------------------------------------
 |   Quick Sort
 *----------------------------------------------------------
 |
 |   Time Complexity 
 |      . Best: O(n log n)
 |      . Aver: O(n log n)
 |      . Worst: O(n^2) 
 | 
 |   Space Complexity
 |      . O(log n)
 |
 |   Divide And Conquer Sort
 |   UnStable Sort
 |
 |   Better Space Complexity Than Merge Sort
 |   Time Complexity Worst Case Is Worse Than Merge Sort
 |   Merge Sort is A Stable Sort While Quick Sort is an Unstable Sort
 |
 */


const QuickSort = (items = [], left = [], right = []) => {
    if (items.length < 2) return items

    let [pivot, ...list] = items
    list.forEach(item => (item < pivot ? left : right).push(item))

    return [...QuickSort(left, [], []), pivot, ...QuickSort(right, [], [])]
}


module.exports = QuickSort