43.implement-Quick-Sort.md

43. implement Quick Sort

Problem

https://bigfrontend.dev/problem/implement-Quick-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Quick Sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function quickSort(arr) {
  quickSortImpl(arr, 0, arr.length - 1);
}

function quickSortImpl(arr, low, high) {
  if (low >= high) {
    return;
  }

  const pivotIndex = partition(arr, low, high);
  quickSortImpl(arr, low, pivotIndex - 1);
  quickSortImpl(arr, pivotIndex + 1, high);
}

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

  [arr[i], arr[high]] = [arr[high], arr[i]];
  return i;
}