Card 05/ 09
Quicksort in Python, Java and TypeScript
Lomuto partition, a seeded random pivot, and a loop over the larger side, printing each partition.
A practical quicksort is three pieces: a partition that picks a random pivot and swaps it to the end before the Lomuto scan, a sorting function that recurses into the smaller side and loops over the larger, and a source of random numbers. The listings below use a Lehmer generator, which multiplies its state by 48271 and keeps the remainder after dividing by 2³¹ − 1. It is written out in each language and seeded with 42, so that all three pick the same pivots and print the same lines; real code would use the language's own random source. Each listing sorts 7 2 8 1 5 3 6, prints every partition as the range before and after, and checks the result against the built-in sort.
Quicksort with a random pivot and a loop over the larger side, in each language
class Lehmer:
def __init__(self, seed: int) -> None:
self.state = seed
def below(self, bound: int) -> int:
self.state = self.state * 48271 % 2147483647
return self.state % bound
def quicksort(items: list[int], rng: Lehmer) -> None:
sort_range(items, 0, len(items) - 1, rng)
def sort_range(items: list[int], low: int, high: int, rng: Lehmer) -> None:
while low < high:
p = partition(items, low, high, rng)
if p - low < high - p:
sort_range(items, low, p - 1, rng)
low = p + 1
else:
sort_range(items, p + 1, high, rng)
high = p - 1
def partition(items: list[int], low: int, high: int, rng: Lehmer) -> int:
before = " ".join(map(str, items[low:high + 1]))
chosen = low + rng.below(high - low + 1)
items[chosen], items[high] = items[high], items[chosen]
pivot, i = items[high], low
for j in range(low, high):
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[high] = items[high], items[i]
print(f"partition {before} around {pivot} -> {' '.join(map(str, items[low:high + 1]))}")
return i
seed = 42
print("seed:", seed)
numbers = [7, 2, 8, 1, 5, 3, 6]
quicksort(numbers, Lehmer(seed))
print("sorted:", " ".join(map(str, numbers)))
print("built-in:", " ".join(map(str, sorted([7, 2, 8, 1, 5, 3, 6]))))seed: 42
partition 7 2 8 1 5 3 6 around 7 -> 6 2 1 5 3 7 8
partition 6 2 1 5 3 around 1 -> 1 2 3 5 6
partition 2 3 5 6 around 3 -> 2 3 5 6
partition 5 6 around 6 -> 5 6
sorted: 1 2 3 5 6 7 8
built-in: 1 2 3 5 6 7 8import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class QuicksortCode {
static final class Lehmer {
private long state;
Lehmer(long seed) {
state = seed;
}
int below(int bound) {
state = state * 48271 % 2147483647;
return (int) (state % bound);
}
}
static void quicksort(int[] items, Lehmer rng) {
sortRange(items, 0, items.length - 1, rng);
}
static void sortRange(int[] items, int low, int high, Lehmer rng) {
while (low < high) {
int p = partition(items, low, high, rng);
if (p - low < high - p) {
sortRange(items, low, p - 1, rng);
low = p + 1;
} else {
sortRange(items, p + 1, high, rng);
high = p - 1;
}
}
}
static int partition(int[] items, int low, int high, Lehmer rng) {
String before = join(items, low, high + 1);
swap(items, low + rng.below(high - low + 1), high);
int pivot = items[high];
int i = low;
for (int j = low; j < high; j++) {
if (items[j] < pivot) {
swap(items, i, j);
i++;
}
}
swap(items, i, high);
System.out.println("partition " + before + " around " + pivot + " -> " + join(items, low, high + 1));
return i;
}
static void swap(int[] items, int a, int b) {
int held = items[a];
items[a] = items[b];
items[b] = held;
}
static String join(int[] values, int from, int to) {
return IntStream.range(from, to).mapToObj(index -> String.valueOf(values[index]))
.collect(Collectors.joining(" "));
}
public static void main(String[] args) {
long seed = 42;
System.out.println("seed: " + seed);
int[] numbers = {7, 2, 8, 1, 5, 3, 6};
quicksort(numbers, new Lehmer(seed));
System.out.println("sorted: " + join(numbers, 0, numbers.length));
int[] copy = {7, 2, 8, 1, 5, 3, 6};
Arrays.sort(copy);
System.out.println("built-in: " + join(copy, 0, copy.length));
}
}seed: 42
partition 7 2 8 1 5 3 6 around 7 -> 6 2 1 5 3 7 8
partition 6 2 1 5 3 around 1 -> 1 2 3 5 6
partition 2 3 5 6 around 3 -> 2 3 5 6
partition 5 6 around 6 -> 5 6
sorted: 1 2 3 5 6 7 8
built-in: 1 2 3 5 6 7 8class Lehmer {
private state: number;
constructor(seed: number) {
this.state = seed;
}
below(bound: number): number {
this.state = (this.state * 48271) % 2147483647;
return this.state % bound;
}
}
function quicksort(items: number[], rng: Lehmer): void {
sortRange(items, 0, items.length - 1, rng);
}
function sortRange(items: number[], low: number, high: number, rng: Lehmer): void {
while (low < high) {
const p = partition(items, low, high, rng);
if (p - low < high - p) {
sortRange(items, low, p - 1, rng);
low = p + 1;
} else {
sortRange(items, p + 1, high, rng);
high = p - 1;
}
}
}
function partition(items: number[], low: number, high: number, rng: Lehmer): number {
const before = items.slice(low, high + 1).join(" ");
swap(items, low + rng.below(high - low + 1), high);
const pivot = items[high];
let i = low;
for (let j = low; j < high; j++) {
if (items[j] < pivot) {
swap(items, i, j);
i++;
}
}
swap(items, i, high);
console.log(`partition ${before} around ${pivot} -> ${items.slice(low, high + 1).join(" ")}`);
return i;
}
function swap(items: number[], a: number, b: number): void {
[items[a], items[b]] = [items[b], items[a]];
}
const seed = 42;
console.log(`seed: ${seed}`);
const numbers = [7, 2, 8, 1, 5, 3, 6];
quicksort(numbers, new Lehmer(seed));
console.log(`sorted: ${numbers.join(" ")}`);
const builtIn = [7, 2, 8, 1, 5, 3, 6].sort((a, b) => a - b);
console.log(`built-in: ${builtIn.join(" ")}`);seed: 42
partition 7 2 8 1 5 3 6 around 7 -> 6 2 1 5 3 7 8
partition 6 2 1 5 3 around 1 -> 1 2 3 5 6
partition 2 3 5 6 around 3 -> 2 3 5 6
partition 5 6 around 6 -> 5 6
sorted: 1 2 3 5 6 7 8
built-in: 1 2 3 5 6 7 8All three printed the same seven lines. Seed 42 picked 7 as the first pivot, and it landed at index 5 with one item, 8, to its right. That side is the smaller, so the recursive call sorts it, returning at once because one item is already sorted, and the loop carries on with the five items on the left.
The highlighted lines are the ones that matter. The first compares the sizes of the two sides, p - low items on the left and high - p on the right, and recurses into the smaller one; the other side is handled by moving low or high and going round the while loop. The second picks the pivot's index uniformly from the range and swaps that item to the end, so the Lomuto scan that follows is the textbook one. The third is the comparison, <, which sends items equal to the pivot to its right.
In real code, use the built-in sort. Java's Arrays.sort on an int[] is a dual-pivot quicksort, which partitions around two pivots into three parts and switches to heapsort if the recursion runs too deep, so it stays O(n log n) in the worst case; on an array of objects it is a stable merge-based sort, because quicksort is not stable. Python's sorted and TypeScript's sort are stable merge-based sorts, not quicksorts. Choosing a Sorting Algorithm, a later topic, covers what each built-in runs and when that matters.
← → move through sections and cards