Card 07/ 11
Bucket Sort in Python, Java and TypeScript
Bucket sort over a known range, printing each bucket before and after it is sorted, and the comparisons it took.
A bucket sort is a list of lists: one loop drops each key into its bucket, and a second sorts each bucket and appends it to the output. The listings below sort two inputs with five buckets over the range 0 to 14. The first, 13 4 10 7 14 3 10, is spread across the range; the second, 14 13 12 14 13 12 14, is gathered at its top. Each run prints every bucket before and after its insertion sort, and the total number of comparisons the insertion sorts made.
Bucket sort with insertion sort inside each bucket, in each language
def bucket_sort(items: list[int], low: int, high: int, bucket_count: int) -> list[int]:
width = high - low + 1
buckets: list[list[int]] = [[] for _ in range(bucket_count)]
for value in items:
buckets[(value - low) * bucket_count // width].append(value)
comparisons = 0
output: list[int] = []
for index, bucket in enumerate(buckets):
before = show(bucket)
comparisons += insertion_sort(bucket)
print(f"bucket {index}: {before} -> {show(bucket)}")
output.extend(bucket)
print("comparisons:", comparisons)
return output
def insertion_sort(bucket: list[int]) -> int:
comparisons = 0
for i in range(1, len(bucket)):
key = bucket[i]
j = i - 1
while j >= 0:
comparisons += 1
if bucket[j] <= key:
break
bucket[j + 1] = bucket[j]
j -= 1
bucket[j + 1] = key
return comparisons
def show(values: list[int]) -> str:
return " ".join(map(str, values)) or "empty"
for label, numbers in (("evenly spread", [13, 4, 10, 7, 14, 3, 10]), ("gathered", [14, 13, 12, 14, 13, 12, 14])):
print(label)
result = bucket_sort(numbers, 0, 14, 5)
print("sorted:", show(result))
print("built-in:", show(sorted(numbers)))evenly spread
bucket 0: empty -> empty
bucket 1: 4 3 -> 3 4
bucket 2: 7 -> 7
bucket 3: 10 10 -> 10 10
bucket 4: 13 14 -> 13 14
comparisons: 3
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14
gathered
bucket 0: empty -> empty
bucket 1: empty -> empty
bucket 2: empty -> empty
bucket 3: empty -> empty
bucket 4: 14 13 12 14 13 12 14 -> 12 12 13 13 14 14 14
comparisons: 13
sorted: 12 12 13 13 14 14 14
built-in: 12 12 13 13 14 14 14import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BucketCode {
static List<Integer> bucketSort(int[] items, int low, int high, int bucketCount) {
int width = high - low + 1;
List<List<Integer>> buckets = new ArrayList<>();
for (int index = 0; index < bucketCount; index++) {
buckets.add(new ArrayList<>());
}
for (int value : items) {
buckets.get((value - low) * bucketCount / width).add(value);
}
int comparisons = 0;
List<Integer> output = new ArrayList<>();
for (int index = 0; index < bucketCount; index++) {
List<Integer> bucket = buckets.get(index);
String before = show(bucket);
comparisons += insertionSort(bucket);
System.out.println("bucket " + index + ": " + before + " -> " + show(bucket));
output.addAll(bucket);
}
System.out.println("comparisons: " + comparisons);
return output;
}
static int insertionSort(List<Integer> bucket) {
int comparisons = 0;
for (int i = 1; i < bucket.size(); i++) {
int key = bucket.get(i);
int j = i - 1;
while (j >= 0) {
comparisons++;
if (bucket.get(j) <= key) {
break;
}
bucket.set(j + 1, bucket.get(j));
j--;
}
bucket.set(j + 1, key);
}
return comparisons;
}
static String show(List<Integer> values) {
return values.isEmpty() ? "empty" : values.stream().map(String::valueOf).collect(Collectors.joining(" "));
}
public static void main(String[] args) {
String[] labels = {"evenly spread", "gathered"};
int[][] inputs = {{13, 4, 10, 7, 14, 3, 10}, {14, 13, 12, 14, 13, 12, 14}};
for (int run = 0; run < inputs.length; run++) {
System.out.println(labels[run]);
System.out.println("sorted: " + show(bucketSort(inputs[run], 0, 14, 5)));
int[] copy = inputs[run].clone();
Arrays.sort(copy);
System.out.println("built-in: " + show(Arrays.stream(copy).boxed().toList()));
}
}
}evenly spread
bucket 0: empty -> empty
bucket 1: 4 3 -> 3 4
bucket 2: 7 -> 7
bucket 3: 10 10 -> 10 10
bucket 4: 13 14 -> 13 14
comparisons: 3
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14
gathered
bucket 0: empty -> empty
bucket 1: empty -> empty
bucket 2: empty -> empty
bucket 3: empty -> empty
bucket 4: 14 13 12 14 13 12 14 -> 12 12 13 13 14 14 14
comparisons: 13
sorted: 12 12 13 13 14 14 14
built-in: 12 12 13 13 14 14 14function bucketSort(items: number[], low: number, high: number, bucketCount: number): number[] {
const width = high - low + 1;
const buckets: number[][] = Array.from({ length: bucketCount }, () => []);
for (const value of items) {
buckets[Math.floor(((value - low) * bucketCount) / width)].push(value);
}
let comparisons = 0;
const output: number[] = [];
buckets.forEach((bucket, index) => {
const before = show(bucket);
comparisons += insertionSort(bucket);
console.log(`bucket ${index}: ${before} -> ${show(bucket)}`);
output.push(...bucket);
});
console.log(`comparisons: ${comparisons}`);
return output;
}
function insertionSort(bucket: number[]): number {
let comparisons = 0;
for (let i = 1; i < bucket.length; i++) {
const key = bucket[i];
let j = i - 1;
while (j >= 0) {
comparisons++;
if (bucket[j] <= key) {
break;
}
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
return comparisons;
}
function show(values: number[]): string {
return values.length === 0 ? "empty" : values.join(" ");
}
const runs: [string, number[]][] = [
["evenly spread", [13, 4, 10, 7, 14, 3, 10]],
["gathered", [14, 13, 12, 14, 13, 12, 14]],
];
for (const [label, numbers] of runs) {
console.log(label);
console.log(`sorted: ${show(bucketSort(numbers, 0, 14, 5))}`);
console.log(`built-in: ${show([...numbers].sort((a, b) => a - b))}`);
}evenly spread
bucket 0: empty -> empty
bucket 1: 4 3 -> 3 4
bucket 2: 7 -> 7
bucket 3: 10 10 -> 10 10
bucket 4: 13 14 -> 13 14
comparisons: 3
sorted: 3 4 7 10 10 13 14
built-in: 3 4 7 10 10 13 14
gathered
bucket 0: empty -> empty
bucket 1: empty -> empty
bucket 2: empty -> empty
bucket 3: empty -> empty
bucket 4: 14 13 12 14 13 12 14 -> 12 12 13 13 14 14 14
comparisons: 13
sorted: 12 12 13 13 14 14 14
built-in: 12 12 13 13 14 14 14All three printed the same lines. The spread input filled four of the five buckets with at most two keys each, and the insertion sorts made 3 comparisons. The gathered input put all seven keys in bucket 4, left the other four empty, and made 13 comparisons: the bucket sort did nothing but run one insertion sort over the whole input.
The first highlighted line computes the bucket. Multiplying before dividing keeps the arithmetic in integers, and the result is always between 0 and bucket_count − 1 because the key is at most high. The second highlighted line is the insertion sort's test, and it uses <= so that an equal key stops the shift and stays behind the earlier one, which keeps the sort stable.
None of the three languages has a bucket sort in its standard library, and for good reason: a bucket sort needs the range and the spread of the keys, which a general sort cannot know. In real code it appears where those are known, such as sorting floating-point values from a uniform source, or as the first step of a larger algorithm that spreads work across machines.
← → move through sections and cards