JavaScript Implementation of Quick Sort (Hoare Partition Scheme)

quick-sort-hoare-partition-scheme.js

// https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
function quickSort(arr, lo, hi) {
  if (lo >= 0 && hi >= 0 && lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p);
    quickSort(arr, p + 1, hi);
  }
}

function partition(arr, lo, hi) {
  const pivot = arr[Math.floor((lo + hi) / 2)];
  let i = lo - 1;
  let j = hi + 1;
  while (true) {
    do {
        i++;
    } while (arr[i] < pivot);

    do {
        j--;
    } while (arr[j] > pivot);

    if (i >= j) {
      return j;
    }

    swap(arr, i, j);
  }
}

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

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

this implementation is not entirely correct, if the array contains duplicate elements, page will fall into infinite loop. should use do while as same as Hoare_partition_scheme

Hi @JunQu, I have updated the gist. Thanks for pointing it out!

Thanks, man. I tried to integrate your code into my and add some features... and I lost maybe two or three hours to fix the problems.

Your script is #@!)) Sorry. Try it with random generated array, and array with repeatable numbers.
Surprise — it doesnt work and goes to recursion.

Finally I used this one... https://itnext.io/a-sort-of-quick-guide-to-quicksort-and-hoares-partitioning-scheme-in-javascript-7792112c6d1