Quicksort

in-place-iterative-quicksort.ts

type Slice = [lowIndex: number, highIndex: number];

function getRandomIntegerInRange([low, high]: Slice): number {
  return Math.floor(Math.random() * (high - low + 1)) + low;
}

function createPartitionForSlice([lowIndex, highIndex]: Slice) {
  return function partition(pivotIndex: number, items: number[]): number {
    // Partitioning a slice works like so:
    // - We get the pivot value from the pivot index (in our case, a random index
    //   that was passed in).
    // - We move the pivot value to the end of the slice so it is easier to avoid.
    // - We iterate over the slice, swapping any values less than the pivot value,
    //   so that they are at the beginning of the slice. (Note: they are not sorted.)
    // - Finally, we move the pivot value that we placed at the end of the slice to
    //   the end of the values less than the pivot value (the `nextLowElementIndex`)
    //   and we then return this new pivot index.
    const pivotValue = items[pivotIndex];

    [items[pivotIndex], items[highIndex]] = [
      items[highIndex],
      items[pivotIndex],
    ];

    let nextLowElementIndex = lowIndex;
    for (let i = lowIndex; i < highIndex; i++) {
      if (items[i] < pivotValue) {
        [items[nextLowElementIndex], items[i]] = [
          items[i],
          items[nextLowElementIndex],
        ];
        nextLowElementIndex++;
      }
    }

    const finalPivotIndex = nextLowElementIndex;
    [items[finalPivotIndex], items[highIndex]] = [
      items[highIndex],
      items[finalPivotIndex],
    ];

    return finalPivotIndex;
  };
}

// This demonstrates the iterative in-place quicksort algorithm.
function quicksort(items: number[]): void {
  if (items.length <= 1) {
    return;
  }

  // We start the `stack` with a slice encompassing the entire array.
  const initialSlice: Slice = [0, items.length - 1];
  const stack = [initialSlice];
  while (stack.length > 0) {
    const [lowIndex, highIndex] = stack.pop()!;

    // Our in-place partition function will operate upon a specific slice
    // of the array. We use a higher-order function for expressivity.
    const partition = createPartitionForSlice([lowIndex, highIndex]);

    // In order to avoid worst-case performance (O(n^2)) when an array
    // has already been sorted we randomize the pivot index.
    const pivotIndex = getRandomIntegerInRange([lowIndex, highIndex]);

    // We partition the slice in-place and get the new pivot index
    // that the pivot value is now at after it has been moved.
    //
    // After execution the chosen slice within `items` is partitioned so 
    // that it contains two future slices and the pivot:
    //
    // 1. items[lowIndex..newPivotIndex - 1] contains values less than the pivot value
    // 2. items[newPivotIndex] contains the pivot value
    // 3. items[newPivotIndex + 1..highIndex] contains values greater than the pivot value
    const newPivotIndex = partition(pivotIndex, items);

    // We now push the less-than and greater-than slices onto the stack as long as they
    // contain more than one item.
    //
    // - The slices do not contain the pivot itself since after a partition this is positioned
    //   in its correct, sorted position relative to the entire array.
    // - Slices with one item only are already sorted and therefore not added onto the stack.
    // - Once we no longer have slices in the `stack`, the `items` array is fully sorted.
    if (newPivotIndex - lowIndex > 1) {
      stack.push([lowIndex, newPivotIndex - 1]);
    }

    if (highIndex - newPivotIndex > 1) {
      stack.push([newPivotIndex + 1, highIndex]);
    }
  }
}

// Test 1
const data = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];

quicksort(data);

console.log(data);

// Test 2
const data2 = [
  8, 99, 998, 17, 10, 68, 2, 10021, 6, 2, 4, 234, 9, 456, 1, 2, 3, 9, 7, 5, 9,
  3, 6, 5,
];

quicksort(data2);

console.log(data2);

A follow-up to my original recursive definition: https://gist.github.com/sebinsua/c276318ea96595f8bb62715f23075e06