16. Quick Sort.js

// QUICK SORT
// Escolhe um elemento pivô e joga a esquerda todos os números menores e a direita todos os números maiores e retorna o índice do elemento pivô, repetindo esse processo com todos os elementos, tanto na direita quanto na esquerda.
// Time: best and average: O(n log n) / worst: O(n²)
// Space: O(log n)

function pivot(arr, start = 0, end = arr.length - 1) {
    const swap = (arr, idx1, idx2) => {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    };

    // We are assuming the pivot is always the first element
    let pivot = arr[start];
    let swapIdx = start;

    for (let i = start + 1; i <= end; i++) {
        if (pivot > arr[i]) {
            swapIdx++;
            swap(arr, swapIdx, i);
        }
    }

    // Swap the pivot from the start the swapPoint
    swap(arr, start, swapIdx);
    return swapIdx;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr, left, pivotIndex - 1);
        //right
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}

quickSort([100, -3, 2, 4, 6, 9, 1, 2, 5, 3, 23])