なぜどんなソートも n log n を超えられないのか
ルール
いくつものアルゴリズムが、同じようにシャッフルされたデータを並べ替えます。どれもそれぞれのやり方で、混沌を秩序に変えます。
クリックするとYouTubeから再生されます。
8 Sorting Algorithms Visualized 30 Min Ambient Focus Loop
なぜそうなるのか
トランプをシャッフルして、2枚ずつ比べながら並べ替えます。となり同士を何度も比べる方法もあれば、山を半分に、そのまた半分にと分けていく方法もあります。同じシャッフルなら、後者のほうがずっと早く終わります。そして、比べるだけの方法では、それより大きく速くすることはできません。
比較回数 ≥ log₂(n!) ≈ n·log₂ n − 1.44·nバブルソート：最大 n·(n − 1) ÷ 2
自分で作る
Python 3 · numpy · matplotlib同じシャッフルされたリストに4つのソート。それぞれの比較回数を数えます。
"""Sorting race: four algorithms on the same shuffled list, counting their comparisons.
Run: python sorting-race.py (needs: pip install numpy matplotlib)
"""
import math
import numpy as np
import matplotlib.pyplot as plt
plt.style.use("dark_background")
n = 100
data = list(np.random.default_rng().permutation(n))
count = {"comparisons": 0}
def less(a, b): # every algorithm compares only through this, so we can count
count["comparisons"] += 1
return a < b
def bubble(xs):
xs = xs[:]
for end in range(len(xs) - 1, 0, -1):
for i in range(end):
if less(xs[i + 1], xs[i]):
xs[i], xs[i + 1] = xs[i + 1], xs[i]
return xs
def insertion(xs):
xs = xs[:]
for i in range(1, len(xs)):
j = i
while j > 0 and less(xs[j], xs[j - 1]):
xs[j], xs[j - 1] = xs[j - 1], xs[j]
j -= 1
return xs
def merge(xs):
if len(xs) < 2:
return xs
left, right = merge(xs[: len(xs) // 2]), merge(xs[len(xs) // 2 :])
out = []
while left and right:
out.append(left.pop(0) if not less(right[0], left[0]) else right.pop(0))
return out + left + right
def quick(xs):
if len(xs) < 2:
return xs
pivot, rest = xs[0], xs[1:]
smaller = [x for x in rest if less(x, pivot)]
return quick(smaller) + [pivot] + quick([x for x in rest if x not in smaller])
results = {}
for name, sort in [("bubble", bubble), ("insertion", insertion), ("merge", merge), ("quick", quick)]:
count["comparisons"] = 0
assert sort(data) == sorted(data)
results[name] = count["comparisons"]
print(results, "| at least log2(n!) =", math.ceil(math.log2(math.factorial(n))))
plt.figure(figsize=(7, 4))
plt.bar(list(results), list(results.values()), color=["#f0abfc", "#c4b5fd", "#5eead4", "#5eead4"])
plt.axhline(math.log2(math.factorial(n)), color="white", linestyle="--", label="log2(n!): no comparison sort does better")
plt.ylabel(f"comparisons for n = {n}")
plt.legend()
plt.show()
# Try: n = 1000 (bubble sort needs about n*n/2, merge sort about n*log2(n))
試してみよう： n = 1000 にしてみましょう。バブルソートの回数は約100倍、マージソートは約16倍に増えます。
