Quicksort algorithm

Quick Sort is useful for sorting arrays. It is also known as in-place sort (i.e. it doesn’t require any extra storage).

The overall time complexity of Quick Sort is O(nLogn). In the worst case, it makes O(n2) comparisons, though this behavior is rare.

The space complexity of Quick Sort is O(nLogn).

Facts about quicksort

• The best case time complexity is O(nlogn)
• The worst case time complexity is O(n^2)
• Always select the middle element as a pivot
• Quick uses recursive approaches to sort
• It uses divide and conquers to sort
• Quick sort uses stack
• Max space complexity is n
• Min space complexity is O(nLogn)
• In-place sorting algorithms
• Most of the sorting functions in most of the languages are using quicksort

Quicksort code example

const quicksort = (arr) => {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[arr.length - 1];

    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
    }

    return quicksort(left).concat(pivot, quicksort(right));
};

const unsortedList = [23, 45, 16, 37, 3, 99, 22];
const sortedList = quicksort(unsortedList);

console.log('Sorted arr', sortedList); // [3, 16, 22, 23, 37, 45, 99]