JavaScript Implementation of Quick Sort (Lomuto Partition Scheme)

quick-sort-lomuto-partition-scheme.js

// https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

function quickSort(arr, lo, hi) {
    if (lo >= hi || lo < 0) return;
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; ++j) {
    if (arr[j] <= pivot) {
      swap(arr, i, j);
      i++;
    }
  }

  swap(arr, i, hi);

  return i;
}

function swap(arr, i, j) {
  const tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

const arr = [9, 4, 1, 6, 7, 3, 8, 2, 5];
quickSort(arr, 0, arr.length - 1);