仕組み
ソートとは物を順番に並べること——小さい順、A から Z へ。下のアルゴリズムはどれも同じ問題を解きます。 違うのは戦略だけで、あなたが見るのはその戦略です。アルゴリズムを1つ選び(6つ一気見にはレースモード)、入力を選んで再生。エンジンが動くとバーが光ります:黄色は比較、赤は移動・交換、紫はピボット、緑は確定位置です。
操作は動画プレーヤー風です。エンジン自体がそうだからです:スペースで再生・停止、右矢印で1ステップ、R で最初から、N で新しいリスト、S でシャッフル、速度は 0.25× から 8×。 コードパネルが実行中の疑似コードの行を光らせるので、アニメとプログラムが同期します。同じレースを2回: 逆順のリストと、ほぼ整列済みのリスト。挿入ソートが後方集団から先頭に跳ぶ様子を見てください。
6つのアルゴリズム
3つは単純な2次の方法——書きやすく、大規模では苦しい。3つは分割統治や賢いデータ構造で O(n log n) に届く効率的な方法です。下の例はすべて、普通のリストを扱う完全で動く Python です。
バブルソート — 隣との交換
リストをなぞって隣同士を比べ、逆順のペアを交換します。1周ごとに未整列の最大値が最終位置に「泡立ち」、 次の周は1歩短くできます。丸々1周で交換がなければ整列済みで早期終了——それが唯一の取り柄であり、 すでに整列済みの入力で O(n) になる理由です。
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return a選択ソート — 最小を選んで繰り返し
リストを整列済みの前部と未整列の残りに分けます。各ステップで残り全体から最小値を探して定位置へ交換。 入力がどれだけ整っていても比較回数は同じ——約 n²/2。だから最良・平均・最悪すべて O(n²) です。美点は 交換が高々 n 回なことで、交換が高価だった時代に重宝されました。
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a挿入ソート — トランプの並べ方
手札を整えるように:次の1枚を取って、より大きい物の左へ滑らせて収めます。ほぼ整列済みのデータでは ほとんど動かないので O(n)——この条件では場内最速であり、実用のハイブリッドソートが小さな部分列に使う 理由です。逆順データでは全員が全行程を移動:最悪 O(n²)。安定で、余分なメモリは不要です。
def insertion_sort(a):
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マージソート — 分けて、制して、統合
リストを半分に割り、各半分を同じ方法で整列し(再帰は1要素で止まり、定義上整列済み)、整列済みの両半分 の先頭の小さい方から取って統合します。分割は常に均等なので各段 O(n)、段数は log n:全ケースで O(n log n) 保証。代償は統合用の O(n) の余分メモリ。安定です——等しい要素は決して交差しません。
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = 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:]クイックソート — ピボットで分割
ピボットを選び分割:小さい物は左へ、大きい物は右へ。両側を同じ方法で整列。ピボットが 真ん中付近に落ちれば再帰は log n 段、合計 O(n log n)。定数は極小、余分メモリは再帰用の O(log n) だけ——実用上 たいてい最速です。端に落ちると片側がほぼ全部を抱えて O(n²) に悪化。このシミュレータは三値中央値(先頭・中央・末尾)でピボットを選ぶため、実データで悪い場合はまれです。下の Python 例は短くするため、単に末尾の要素をピボットにしています。
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aヒープソート — 変装した優先度付きキュー
リストを最大ヒープに:配列に詰めた二分木で親は子より大きく、最大値が0番に来ます。 最大値を繰り返し取り出して末尾へ交換し、ヒープを1つ縮めて新しい頂点を沈めて性質を回復。O(n log n) 保証、余分メモリ O(1)——でも跳び回るアクセスはプロセッサのキャッシュに嫌われ、紙面上は互角でも計測では クイックやマージに負けがちです。
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return a表の読み方
ビッグオーは成長を表し、ストップウォッチではありません。定数やハードをあえて無視して、スケールの形を見せます。下表は標準の参考資料(Cormen ら Introduction to Algorithms、NIST アルゴリズム・データ構造辞典)。「安定」とは等しい要素が元の順序を保つことです。
| アルゴリズム | 最良 | 平均 | 最悪 | 余分メモリ | 安定 |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | はい |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | いいえ |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | はい |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | はい |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | いいえ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | いいえ |
シミュレータで試そう:6つを逆順リスト、次にほぼ整列済みリストで対戦。ゴール順が ひっくり返り——挿入ソートが後方集団から先頭へ——式で見るより目撃が一番の学びです。
よくある 3 つの間違い
「クイックソートはいつでも最速だ。」平均では最速の部類に入りますが、単純なクイックソートの最悪の場合は O(n²) です。たとえば、ピボットがいつもリストの端に来てしまう場合です。マージソートとヒープソートは、どんな入力でも O(n log n) のままです。
「単純な O(n²) の方法は役に立たない。」挿入ソートは小さなリストによく使われ、ほとんど整列済みのリストではとても速く動きます。実際に使われる整列ルーチンの多くはハイブリッドで、小さな部分には挿入ソートに切り替えます。
「安定ソートとは、決して失敗しないソートのことだ。」安定性には正確な意味があります。キーが等しい要素どうしが、整列の前と同じ順序を保つということです。マージソートと挿入ソートは安定で、クイックソートとヒープソートは、ふつうの実装では安定ではありません。
来館者の質問
実際のコードではどのソートを使えばいい?
ほぼ常に言語標準のソートです:Python の sorted()、JavaScript の Array.sort()、オブジェクトに対する Java の Arrays.sort()。いずれも実戦的なハイブリッド(Python と Java は Timsort)で O(n log n)、安定、何百万人ものユーザーに検証されています。このページの6つは、その道具の背後にある考え方を教えるもので、置き換えるものではありません。
バブルソートは遅いのに、なぜ教えるの?
考えられる最も単純なソートだからです:隣同士を比べて逆なら交換、繰り返し。レースモードでマージソートに苦しむ様子を見ることは、どんな式よりも O(n²) の増え方を教えてくれます。早期終了からは、同じアルゴリズムでも整列済みの入力では O(n)、一般的には O(n²) になることがわかります。
安定なソートとはどういう意味?
安定なソートは、等しい要素の元の相対順序を保ちます。複数のキーで並べるときに重要です:クラスを名前順にしてから安定な方法で成績順にすると、同点の生徒はアルファベット順のままです。マージ、挿入、バブルソートは安定。通常の実装の選択、クイック、ヒープソートは安定ではありません。
平均 O(n log n) なのにクイックソートが常に最速ではないのはなぜ?
最悪ケースが O(n²) だからです:運悪くピボットが外れると、分割のたびに1つしか取り除けません。良い実装は三値中央値ピボット(このシミュレータの方式)やランダム化で回避します。マージソートは O(n log n) を保証しますが O(n) の余分なメモリが必要。ヒープソートは O(n log n) をインプレースで保証しますが、メモリを跳び回るため現代のキャッシュには嫌われます。
シミュレータは本当にアルゴリズムを実行しているの?アニメだけ?
本当に実行しています。各アルゴリズムは本物のロジックで動き、比較・交換・上書き・ピボット・マージ・ヒープ化といったステップイベントを出し、アニメーションのグラフが再生します。レースモードでは6つが同じ入力で並走するので比較は公平です。単語モードはアクセントや大文字小文字を区別せずに並べます。
ビッグオー記法は何を数えているの?
定数因子を無視して、基本ステップ数が入力とともにどう増えるかです。O(n²) は入力を倍にすると手間がほぼ4倍になること。O(n log n) は倍にしても2倍強にしかならないこと。n = 1,000,000 では約1兆回と2千万回の差——数分〜数時間と一瞬の差です。
出典と関連資料
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
この展示を引用する
Eurekarium. (2026). ソートラボ. https://eurekarium.com/ja/computing/sorting-lab/
最終更新: