quickSort.js

function swap(arr, a, b) {
  if (a === b) {
    return;
  }
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

let loops = [];
function quickSort(arr, start, end) {
  start = start || 0;
  end = end >= 0 ? end : arr.length - 1;
  
  const pivot = arr[end];
  let i = start;
  const callTime = loops.length;
  loops[callTime] = 0;
  // console.log('sort', start, end);
  for (let j = start; j < end; j++) {
    loops[callTime]++;
    if (arr[j] < pivot) {
      // console.log('before i<=>j swap', arr, `arr[${i}]=${arr[i]}`, `arr[${j}]=${arr[j]}`);
      swap(arr, j, i);
      i++;
      // console.log('i<=>j swap', arr, i);
    }
  }
  // console.log(
  //   "before pivot swap",
  //   `arr[${i}]=${arr[i]}`,
  //   `arr[${end}]=${arr[end]}`
  // );
  swap(arr, i, end);
  if (end > i + 1) {
    quickSort(arr, i + 1, end);
  }
  if (i - 1 > start) {
    quickSort(arr, start, i - 1);
  }
  return arr;
}

function testQuickSort(arr) {
  loops = [];
  console.log('=== sort ', arr);
  console.log("result: ", quickSort(arr));
  console.log(
    "loops: ",
    loops.length,
    // loops,
    loops.reduce((res, n) => res + n, 0)
  );
}

testQuickSort([6,5,4,3,2,1,0]);
testQuickSort([6,2,0,3,2,4,0]);
testQuickSort([0,1,2,3,4,5,6]);
testQuickSort([1,4,5,3,0,2,6]);