昼夜いつでも開館入場無料展示に触れてみましょう

展示室 F1 · コンピューティング

6つのソートアルゴリズムのレースを見よう。

バブル、選択、挿入、マージ、クイック、ヒープソートを並走させよう。1回1回の比較と交換を見て、なぜ数百万件にスケールするものと脱落するものがあるのかを理解しよう。

仕組み

ソートとは物を順番に並べること——小さい順、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 SortO(n)O(n²)O(n²)O(1)はい
Selection SortO(n²)O(n²)O(n²)O(1)いいえ
Insertion SortO(n)O(n²)O(n²)O(1)はい
Merge SortO(n log n)O(n log n)O(n log n)O(n)はい
Quick SortO(n log n)O(n log n)O(n²)O(log n)いいえ
Heap SortO(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千万回の差——数分〜数時間と一瞬の差です。

出典と関連資料

この展示を引用する

Eurekarium. (2026). ソートラボ. https://eurekarium.com/ja/computing/sorting-lab/

最終更新: