中文
devexamples

Quicksort With Median Of Three Pivot (JavaScript)

Sort an array in place using quicksort with median-of-three pivot selection to avoid worst-case behavior on already sorted or reverse sorted input.

JavascriptData Integrity

Code

snippet
function quicksort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const mid = (lo + hi) >>> 1;
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi] < arr[lo]) [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
  if (arr[mid] < arr[hi]) [arr[hi], arr[mid]] = [arr[mid], arr[hi]];
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  quicksort(arr, lo, i - 1);
  quicksort(arr, i + 1, hi);
  return arr;
}

Related Examples