Quicksort

Quick sort is a divide-and-conquer sorting algorithm that selects a “pivot” element from an array, partitions the remaining elements into two sub-arrays (elements less than the pivot and elements greater than the pivot), and then recursively sorts the sub-arrays.

/**
 * @file Quicksort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Sorts an array using the quicksort algorithm.
 *
 * @param array The array to be sorted.
 * @param start The starting index of the segment of the array to be sorted.
 * @param end The ending index of the segment of the array to be sorted.
 */
function quicksort(array: number[], start: number, end: number): void {
  if (start < end) {
    const pivotIndex = partition(array, start, end);
    quicksort(array, start, pivotIndex - 1);
    quicksort(array, pivotIndex + 1, end);
  }
}

/**
 * Partitions the array into two parts; one with elements less than the pivot
 * and the other with elements greater than the pivot.
 *
 * @param array The array to be partitioned.
 * @param start The starting index of the segment of the array to be
 *   partitioned.
 * @param end The ending index of the segment of the array to be partitioned.
 * @returns The index of the pivot element after partitioning.
 */
function partition(array: number[], start: number, end: number): number {
  const pivot = array[end];
  let i = start - 1;
  for (let index = start; index <= end - 1; index++) {
    if (array[index] <= pivot) {
      i++;
      swap(array, i, index);
    }
  }

swap(array, i + 1, end);
  return i + 1;
}

/**
 * Swaps two elements in an array.
 *
 * @param array The array containing the elements to be swapped.
 * @param index1 The index of the first element to be swapped.
 * @param index2 The index of the second element to be swapped.
 */
function swap(array: number[], index1: number, index2: number): void {
  const temporary = array[index1];
  array[index1] = array[index2];
  array[index2] = temporary;
}

// Usage
(() => {
  const array = [2, 8, 7, 1, 3, 5, 6, 4];
  quicksort(array, 0, array.length - 1);
  const actual = array.toString();
  const expected = '1,2,3,4,5,6,7,8';
  if (actual !== expected) {
    throw new Error(`Expected ${expected} but got ${actual}`);
  }

console.log('Array sorted successfully.');
})();