ソートアルゴリズム発明史：なぜ世界には何十種類もの並べ替えがあるのか

def bubble_sort(a):    a = a.copy()    n = len(a)    for i in range(n):        for j in range(0, n-i-1):            if a[j] > a[j+1]:                a[j], a[j+1] = a[j+1], a[j]    return a
def selection_sort(a):    a = a.copy()    for i in range(len(a)):        m = i + a[i:].index(min(a[i:]))        a[i], a[m] = a[m], a[i]    return a
def insertion_sort(a):    a = a.copy()    for i in range(1, len(a)):        key = a[i]; j = i - 1        while j >= 0 and a[j] > key:            a[j+1] = a[j]; j -= 1        a[j+1] = key    return a
def merge_sort(a):    if len(a) <= 1: return a    mid = len(a) // 2    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])    out, i, j = [], 0, 0    while i < len(left) and j < len(right):        if left[i] <= right[j]:            out.append(left[i]); i += 1        else:            out.append(right[j]); j += 1    return out + left[i:] + right[j:]
# 動作確認import randomdata = [random.randint(0, 100) for _ in range(10)]print("元:", data)print("バブル:", bubble_sort(data))print("マージ:", merge_sort(data))

import time, randomimport matplotlib.pyplot as plt
def measure(sort_fn, n, trials=3):    ts = []    for _ in range(trials):        data = [random.random() for _ in range(n)]        t0 = time.perf_counter()        sort_fn(data)        ts.append(time.perf_counter() - t0)    return min(ts)
sizes_sq = [200, 500, 1000, 2000, 4000, 8000]sizes_nlogn = [1000, 5000, 20000, 100000, 500000]
results = {}for sf in [bubble_sort, selection_sort, insertion_sort]:    results[sf.__name__] = [measure(sf, n) for n in sizes_sq]results["merge_sort"] = [measure(merge_sort, n) for n in sizes_nlogn]results["sorted (Timsort)"] = [measure(lambda a: sorted(a), n) for n in sizes_nlogn]
plt.figure(figsize=(10, 6))for name in ["bubble_sort", "selection_sort", "insertion_sort"]:    plt.loglog(sizes_sq, results[name], "o-", label=f"{name} (O(n²))")for name in ["merge_sort", "sorted (Timsort)"]:    plt.loglog(sizes_nlogn, results[name], "s-", label=f"{name} (O(n log n))")plt.xlabel("Input size n"); plt.ylabel("Time (sec, log)")plt.title("Step 2: O(n²) vs O(n log n) — measured")plt.legend(); plt.grid(alpha=0.3, which="both")plt.show()

import randomdef quick_sort(a):    if len(a) <= 1: return a    pivot = a[len(a)//2]    left  = [x for x in a if x < pivot]    mid   = [x for x in a if x == pivot]    right = [x for x in a if x > pivot]    return quick_sort(left) + mid + quick_sort(right)
print(quick_sort([3,6,1,8,2,9,4,7,5]))

import random, time
n = 200000# 完全にランダムrandom_data  = [random.random() for _ in range(n)]# 半分は既に並んでるpartial_data = sorted(random.random() for _ in range(n//2)) + [random.random() for _ in range(n//2)]
for label, data in [("random", random_data), ("partial", partial_data)]:    t0 = time.perf_counter()    sorted(data)    print(f"sorted({label}): {time.perf_counter()-t0:.3f} s")    t0 = time.perf_counter()    quick_sort(data)    print(f"quick({label}):  {time.perf_counter()-t0:.3f} s")

def radix_sort(a):    a = a.copy()    if not a: return a    max_val = max(a)    exp = 1    while max_val // exp > 0:        # 桁ごとにバケットに振り分ける        buckets = [[] for _ in range(10)]        for x in a:            buckets[(x // exp) % 10].append(x)        a = [x for b in buckets for x in b]        exp *= 10    return a
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))# → [2, 24, 45, 66, 75, 90, 170, 802]