#!/usr/bin/env python3 # bucket-sort-experiment.py (c) afiskon 2026 # https://eax.me/2026/2026-11-18-bucket-sort.html import argparse import random from time import perf_counter import matplotlib.pyplot as plt ALPHABET = "abcdefghijklmnopqrstuvwxyz" STRING_LENGTH = 8 PREFIX_LENGTH = 3 INSERTION_SORT_THRESHOLD = 8 SAMPLE_SIZES = [10, 100, 1000, 10_000, 100_000, 1_000_000, 10_000_000] RUNS_PER_SIZE = 3 PLOT_FILE = "experiment.webp" PLOT_COLORS = { "QS": "#1f6fb4", "QS+IS": "#2ca089", "BS": "#e8742c", } PLOT_DPI = 100 PLOT_WIDTH_PX = 768 PLOT_HEIGHT_PX = 512 def quicksort(arr): _quicksort(arr, 0, len(arr) - 1) def _quicksort(arr, low, high): if low < high: split = _partition(arr, low, high) _quicksort(arr, low, split - 1) _quicksort(arr, split + 1, high) def hybrid_quicksort(arr): _hybrid_quicksort(arr, 0, len(arr) - 1) def _hybrid_quicksort(arr, low, high): if high - low + 1 <= INSERTION_SORT_THRESHOLD: _insertion_sort(arr, low, high) else: split = _partition(arr, low, high) _hybrid_quicksort(arr, low, split - 1) _hybrid_quicksort(arr, split + 1, high) def _partition(arr, low, high): chosen = random.randint(low, high) arr[chosen], arr[high] = arr[high], arr[chosen] pivot = arr[high] i = low for j in range(low, high): if arr[j] < pivot: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[high] = arr[high], arr[i] return i def insertion_sort(arr): _insertion_sort(arr, 0, len(arr) - 1) def _insertion_sort(arr, low, high): for i in range(low + 1, high + 1): key = arr[i] j = i - 1 while j >= low and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key def _bucket_index(s): idx = 0 for i in range(PREFIX_LENGTH): idx = idx * len(ALPHABET) + (ord(s[i]) - ord('a')) return idx def bucket_sort(arr): buckets = [[] for _ in range(len(ALPHABET) ** PREFIX_LENGTH)] for s in arr: buckets[_bucket_index(s)].append(s) pos = 0 for bucket in buckets: if bucket: insertion_sort(bucket) arr[pos:pos + len(bucket)] = bucket pos += len(bucket) def random_strings(size): return [ "".join(random.choices(ALPHABET, k=STRING_LENGTH)) for _ in range(size) ] def check_sorted(arr): for i in range(1, len(arr)): if arr[i - 1] > arr[i]: raise ValueError(f"Array is not sorted at index {i}") print("check_sorted() - passed") def measure(sort_func, size, check): total = 0.0 for _ in range(RUNS_PER_SIZE): arr = random_strings(size) started_at = perf_counter() sort_func(arr) total += perf_counter() - started_at if check: check_sorted(arr) return total / RUNS_PER_SIZE def save_plot(results): fig, ax = plt.subplots( figsize=(PLOT_WIDTH_PX / PLOT_DPI, PLOT_HEIGHT_PX / PLOT_DPI), dpi=PLOT_DPI, ) for name, timings in results.items(): ax.plot(SAMPLE_SIZES, timings, marker='o', color=PLOT_COLORS[name], label=name) ax.set_xscale('log') ax.set_yscale('log') # log, linear ax.set_xlabel("Number of strings") ax.set_ylabel("Sorting time, seconds") ax.legend() fig.tight_layout() fig.savefig(PLOT_FILE, dpi=PLOT_DPI, pil_kwargs={"lossless": True}) plt.close(fig) parser = argparse.ArgumentParser( description="Compare quicksort and bucket sort performance") parser.add_argument('--check', action='store_true', help='check that every sorted array is ordered') args = parser.parse_args() if STRING_LENGTH < PREFIX_LENGTH: raise ValueError(f"STRING_LENGTH should be at least {PREFIX_LENGTH}") algorithms = { "QS": quicksort, "QS+IS": hybrid_quicksort, "BS": bucket_sort, } results = {name: [] for name in algorithms} for size in SAMPLE_SIZES: for name, sort_func in algorithms.items(): elapsed = measure(sort_func, size, args.check) results[name].append(elapsed) print(f"{name}, {size} strings: {elapsed:.6f} sec") save_plot(results) print(f"Plot saved to {PLOT_FILE}")