Categories
interview

Quicksort

Worst Case Time Complexity: O(n^2)

const quickSort = (arr, low, high) => {
  if (low >= 0 && high >= 0 && low < high) {
    const partition = getPartition(arr, low, high);
    quickSort(arr, low, partition);
    quickSort(arr, partition + 1, high);
  }
};

const getPartition = (arr, low, high) => {
  const pivot = arr[low + Math.floor((high - low) / 2)];
  let start = low - 1;
  let end = high + 1;
  while (true) {
    do {
      start++;
    } while (arr[start] < pivot)
    do {
      end--;
    } while (arr[end] > pivot)
    if (start >= end) {
      return end;
    }
    const temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
  }
}

const arr = [4, 3, -1, 4, 1, 0];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

Demo