配列を昇順に並べ替える。sort() を一度呼ぶだけ。あまりに当たり前で、コストなんて意識しません。
でも、コンピュータは中で何をしているのでしょうか。数字を一目で「小さい順」に並べることは、人間には簡単に見えて、機械にはできません。機械にできるのは、たった2つ。2つを比べること、そして2つを入れ替えることです。
並べ替えとは、この比較と交換を、正しい順序になるまで繰り返すことです。そして優れたアルゴリズムとは、この回数をいかに少なく済ませるかの工夫に他なりません。
▶ アニメーションで見たい方はこちら（約10分）
https://youtu.be/GGCDlEWv8XY
この記事では、比較の回数を常に意識しながら、なぜ並べ替えにコストがかかるのか、なぜ賢いやり方が桁違いに速いのかを、底から組み立てます。
バブルソート — 隣を比べて、交換するだけ
まず、最も素朴なやり方から見ていきます。隣り合う2つを比べて、左が大きければ入れ替える。これを左から右へ繰り返します。
1回左から右まで走り切ると、最大の値が、まるで泡のように右端まで押し上げられます。これがバブルソートの名前の由来です。一番大きいものが右端に確定したら、残りでもう一度。次に大きいものが、その隣に確定します。これを繰り返せば、右から順に整列が完成していきます。
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n - 1):
for j in range(n - 1 - i):
comparisons += 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr, comparisons
data = [5, 3, 8, 1, 9, 2]
sorted_data, cmp = bubble_sort(data)
print(sorted_data, "比較回数:", cmp)
隣どうしを比べて交換する。たったこれだけです。仕組みは驚くほど単純です。問題は、その回数にあります。
なぜO(n²)なのか — 比較回数の正体
数えてみましょう。要素がn個あるとき、1回目のパスで比べる回数は n-1。2回目は右端が確定したので n-2。次は n-3。
これを足し合わせると、1+2+3+…という階段状の和になります。その合計は、およそ n の2乗を2で割った数（n(n-1)/2）です。
ここが本質です。要素が10倍になると、比較回数はおよそ100倍になります。これをオーダーnの2乗、O(n²) と呼びます。データが増えると、コストが爆発的に膨らみます。
なぜ2乗なのか。それは「すべての要素を、他のほぼすべての要素と比べている」からです。この無駄に気づくことが、速いアルゴリズムへの第一歩です。
選択ソートと挿入ソート — 発想を変えても2乗の壁は越えられない
別の発想もあります。未整列の中から最小値を1つ選び、先頭に置く。次は2番目に小さいものを選んで、2番目に置く。これが選択ソートです。
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 1パスにつき交換は1回だけ
return arr
バブルソートとの違いは、交換の回数です。バブルは何度も小刻みに入れ替えますが、選択ソートは1パスにつき交換は1回だけ。交換のコストが高い場面では有利です。
しかし、比較の回数は変わりません。最小値を見つけるには、結局すべてを見比べる必要があるからです。比較回数は、やはりn²のままです。発想を変えても、全部と全部を比べる構造が残る限り、2乗の壁は越えられません。
トランプを配られたとき、私たちは無意識に並べ替えています。新しい1枚を、すでに並んだ手札の正しい位置に差し込む。これが挿入ソートです。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 大きい要素を1つずつ右へずらす
j -= 1
arr[j + 1] = key
return arr
配列の左側を「整列済み」と考え、次の1枚を取り出して、後ろから順に比べながら正しい場所まで滑り込ませます。技術的に言えば、挿入位置が見つかるまで、大きい要素を1つずつ右へずらしていく操作です。
ここで面白い性質があります。もとからほぼ整列している配列なら、ずらす回数がほとんどゼロです。挿入ソートはほぼ整列済みのデータで圧倒的に速くなる性質を持っています。この性質は、後で実用ライブラリの設計に効いてきます。
n²の壁 — 100万件で何が起きるか
ここまでの3つは、すべて比較回数がn²でした。小さなデータなら一瞬です。では、現実の規模ではどうでしょうか。
要素が100万件。n²は1兆です。1秒間に10億回比較できる速いマシンでも、およそ1000秒、17分近くかかる計算です。たった一度の並べ替えに、これだけの時間がかかります。
データは増え続けます。2乗のアルゴリズムは、ある規模を超えた瞬間に、現実的に使えなくなります。
ここで問いです。比較を「全部と全部」ではなく、もっと賢く減らす方法はないのでしょうか。答えは、問題を分割することにあります。
分割統治 — 半分に分けるという発想
大きな問題をそのまま解くのは大変です。なら、半分に割ってみましょう。
半分にした2つの山を、それぞれ並べ替える。そしてその2つを賢く合体させれば、全体が並びます。半分の山も、また半分に割る。これを繰り返すと、最後は要素1個の山になり、1個ならもう並んでいます。
ここで鍵になるのが、何回半分にできるかです。100万件は、半分にし続けると、およそ20回で1個になります。1024件なら10回です。これがlog n、対数の正体です。
全部と全部を比べるn²ではなく、n個の要素をlog n段で処理する。これがn × log n の速さを生みます。
マージソート — 分けて、併合する
分割統治を最も素直に実装したのが、マージソートです。
まず配列を、要素1個になるまで半分に割り続けます。ここでは比較も交換も起きません。ただ分けるだけです。
本番はここからの 併合（マージ） です。2つの整列済みの列を1つにまとめるとき、それぞれの先頭だけを比べて、小さい方を取り出す。これを繰り返せば、全体を1回なめるだけで合体できます。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # 先頭同士を比較して小さい方を取り出す
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
なぜ速いのか。各段の併合は、合わせてn個を見るだけです。そして段の数はlog n。だから全体でn × log n。100万件でも、わずか2000万回ほどの比較で済みます。2乗の1兆とは、桁が違います。
クイックソート — 基準で2つに振り分ける
もう一つの代表が、クイックソートです。発想は逆向きの分割統治です。
まず基準となる1つの要素、ピボットを選びます。そして残りを、ピボットより小さいグループと大きいグループに振り分ける。これで、ピボットは最終的な定位置に収まります。
あとは、小さいグループと大きいグループを、それぞれ同じやり方で並べ替えるだけです。再帰的に振り分けを繰り返すと、全体が並びます。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
マージソートが「分けてから併合」なら、クイックソートは「振り分けながら確定」です。追加のメモリがほとんど要らず、実測が非常に速いため、多くの言語の標準で長く使われてきました。
クイックの最悪ケース — なぜn²に戻るのか
クイックソートには弱点があります。ピボットの選び方が悪いと、速さが崩れるのです。
例えば、すでに整列済みの配列で、常に先頭をピボットに選んだらどうなるでしょうか。ピボットより小さいグループは空、大きいグループは残り全部になります。分割が、たった1つずつしか進みません。
これは、半分に割れていない、ということです。段の数がlog nではなくnになり、計算量はn²に逆戻りします。せっかくの分割統治が台無しです。
だから実用のクイックソートは、ピボットをランダムに選んだり、3つの候補の中央値を選んだりして、偏った分割を避ける工夫をしています。
計算量を一望する
ここで一度、全体を見渡しましょう。
| アルゴリズム | 平均計算量 | 最悪計算量 | 追加メモリ | 安定性 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | O(1) | 安定 |
| 選択ソート | O(n²) | O(n²) | O(1) | 不安定 |
| 挿入ソート | O(n²) | O(n²) | O(1) | 安定 |
| マージソート | O(n log n) | O(n log n) | O(n) | 安定 |
| クイックソート | O(n log n) | O(n²) | O(log n) | 不安定 |
バブル、選択、挿入はn²。マージとクイックはn × log n。最初は大差なく見えても、データが大きいほど、2乗組はみるみる引き離されていきます。
万能の最強アルゴリズムは存在しません。あるのは、状況ごとの最適だけです。
実用ライブラリの正体 — なぜTimsortなのか
では、PythonやJavaの標準ソートは、何を使っているのでしょうか。答えは、単一のアルゴリズムではありません。Timsortという、組み合わせ戦略です。
Timsortの発想はこうです。現実のデータは、完全にランダムなことは少なく、部分的に整列済みなことが多い。そこで、すでに並んでいる連続部分（ラン）を見つけ、それを土台にします。
短い部分には、ほぼ整列済みで高速な挿入ソートを使い、それらをマージソートの併合で賢くまとめます。挿入ソートの「ほぼ整列で速い」性質と、マージソートの「最悪でもn log n」の保証を、いいとこ取りしているのです。
実際、PythonとJavaはどちらもTimsortを標準ソートに採用しています（Pythonのsorted()/list.sort()、JavaのCollections.sort()が対象オブジェクト配列に対して使用）。理論の最速だけでなく、現実のデータの形に最適化する。これが実用アルゴリズムの設計思想です。
# Python の sorted() は Timsort。挙動を確認するだけなら実装は不要
data = [5, 3, 8, 1, 9, 2, 3, 3]
print(sorted(data)) # [1, 2, 3, 3, 3, 5, 8, 9]
まとめ
ソートアルゴリズムは、たくさんあるように見えて、根っこは1つでした。比較と交換を、いかに少なく済ませるか、という一点です。
全部と全部を比べる素朴なやり方はn²。問題を半分に割り続ける分割統治はn × log n。そして実用は、データの性質を突いて、理論と現実のいいとこ取りをします。
sort() という一行の裏には、こうした工夫の積み重ねがあります。次にソートを呼ぶとき、中で比較と交換ができるだけ少なく繰り返されている様子を、思い浮かべられるはずです。
チャンネル: https://www.youtube.com/@base-technology （根本解説シリーズ）