This algorithm works by selecting a pivot element (the right-most element in the array) and pushing all elements smaller than it before it in the array.
Thus the pivot element is in its final position in the array.
We repeat this for both the left and right sub-arrays of the pivot element.
function partition(arr, l, r) {
let pivot = arr[r];
let i = l - 1;
for (let j = l; j <= r - 1; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
return i + 1;
}
function quickSort(arr, l, r) {
if (l < r) {
let pivotI = partition(arr, l, r);
quickSort(arr, l, pivotI - 1);
quickSort(arr, pivotI + 1, r);
}
}