← back to index

Quick Sort

An in-place quicksort in TypeScript, with a note on why a left-side pivot forces right-to-left scanning.

published Mar 05, 2019 tags #algorithms #sorting

~/posts/quick-sort $ cat post.md

/ LANG EN / 中文
/ THEME / /

There are already plenty of quicksort writeups. This post just nails down a few details.

  • One of quicksort’s selling points is in-place sorting. The variants that need extra space defeat the purpose.
  • When the pivot is taken from the leftmost element, scanning must start from the right.
  • Quicksort isn’t stable — duplicate elements can swap relative position.

Code

In-place quicksort in TypeScript:

const swap = <T>(arr: T[], left: number, right: number): void => {
    const temp: T = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
};

const quickSort = <T>(
    arr: T[],
    left: number = 0,
    right: number = arr.length - 1,
): void => {
    if (left > right) {
        return;
    }

    let lp: number = left;
    let rp: number = right;

    const pivot: T = arr[left]; // pivot from the left

    while (lp != rp) {
        // While pointers haven't met, scan right-to-left for the
        // next value smaller than pivot.
        while (lp < rp && arr[rp] >= pivot) {
            rp--;
        }
        // Then scan left-to-right for the next value larger than
        // pivot.
        while (lp < rp && arr[lp] <= pivot) {
            lp++;
        }
        // Swap them so the smaller side lands on the left.
        if (lp < rp) {
            swap(arr, lp, rp);
        }
    }

    // Drop the pivot into its final spot.
    arr[left] = arr[lp];
    arr[lp] = pivot;

    // Recurse on both sides.
    quickSort(arr, left, lp - 1);
    quickSort(arr, lp + 1, right);
};

Why scan from the right

Take 9 10 5 7.

  1. Pivot is the leftmost: 9.
  2. Scan right-to-left for a value smaller than 9: 7.
  3. Scan left-to-right for a value larger than 9: 10. Swap to get 9 7 5 10.
  4. Scan right-to-left for a value smaller than 9: 5.
  5. Scan left-to-right for a value larger than 9 — the left pointer meets the right pointer at 5. Swap pivot with the pointer position to get 5 7 9 10. Done.

Step 4 is the punchline. If you scanned left-to-right first, the left pointer would stop at 10. Swapping pivot to that slot would place a larger value on the pivot’s spot and break the partition. Left pivot forces right-first scanning; right pivot forces the reverse.

← back to index