Dustin Boston

/**
 * @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.
 */
export 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.
 */
export 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.
 */
export 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.");
})();

/*!
 * @file Implements algorithm in TypeScript.
 * @author Dustin Boston <mail@dustin.boston>
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 * *Introduction to Algorithms*. (2nd ed). The MIT Press.
 */

import {quicksort} from "../../../../data/algorithms/src/quicksort.ts";
import {assertEquals} from "$assert";

test("Basic test", () => {
  const A = [2, 8, 7, 1, 3, 5, 6, 4];
  quicksort(A, 0, A.length - 1);
  assertEquals(A.toString(), "1,2,3,4,5,6,7,8");
});