Coding Challenge Practice - Question 96

The task is to implement quicksort.

The boilerplate code

function quickSort(arr) {
  // your code here
}

If the array is empty or has one element, it is already sorted.

if (arr.length <= 1) return arr;

The last element is chosen as the pivot

const pivot = arr[high];
let i = low;

i tracks where the next smaller element should go. Loop through the array, and any value smaller than the pivot is swapped to the front.

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

The pivot is left in a sorted position. Everything smaller is to the left, everything bigger is to the right

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

Split the array into two smaller parts

const pivotIndex = partition(low, high);

Recursively sort the left and right sides of the pivot

sort(low, pivotIndex - 1);
sort(pivotIndex + 1, high);

Each recursive call works on a smaller range, so recursion always progresses towards termination.

The final code

function quickSort(arr) {
  // your code here
  if(arr.length <= 1) return arr;

  function partition(low, high) {
    const pivot = arr[high];
    let i = low;

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

    const pivotIndex = partition(low, high);
    sort(low, pivotIndex - 1);
    sort(pivotIndex + 1, high); 
  }
  sort(0, arr.length - 1);
  return arr;
}

That's all folks!