基本のソート — バブル・選択・挿入

バラバラの32本のバーが、たった2つの操作 — 比較と交換 — の繰り返しだけで整列していく。3つの古典ソートを動かして見比べ、最後は同じ配列で競走させて、それぞれの個性を発見します。

1. 並べ替えは「比較」と「交換」でできている

コンピュータは配列全体を一目で見渡すことができません。できるのは「2つの値を比べる」ことと「2つの値を入れ替える」ことだけ。ソートアルゴリズムとは、この2つの基本操作をどんな順番で繰り返すかの手順書です。

いちばん素朴なのがバブルソート。左端から隣同士を比べて、逆順なら交換しながら右へ進みます。1周（1パス）すると、いちばん大きい値が泡（バブル）のように右端まで浮かび上がって確定します。これを未確定部分がなくなるまで繰り返すだけです。

バブルソート — 泡のように大きい値が右へ浮かぶ
比較 0 回 / 交換 0 回
黄色＝いま比べている隣同士のペア、赤＝交換中、緑＝位置が確定したバー。「1手すすめる」で1比較ずつじっくり追えます。カウンタを見ると、32本でも比較が500回近く必要なことが分かります。
POINT — 1パスごとに「確定」が増える 1パス目で最大値が右端に、2パス目で2番目の値がその左に…と、パスのたびに右側の確定ゾーン（緑）が1つ育つ。だから比べる範囲はどんどん狭くてよい。途中のパスで交換が1回も起きなければ「もう整列済み」と分かり、そこで打ち切れる。

2. やり方はひとつじゃない — 選択ソートと挿入ソート

同じ「比較と交換」でも、手順の設計思想が変わると動きはガラリと変わります。

下のデモで方式を切り替えて、同じ配列がどう並べ替わるか見比べてください。

選択ソート vs 挿入ソート — 同じ配列で動きを見比べる
選択ソート：青い帯がスキャン範囲、紫が「いまの最小値」。挿入ソート：浮いている札が「手に持ったカード」、緑が整列済みの手札。同じ配列でも確定のしかたがまったく違います。
POINT — 安定ソートとは 同じ値が複数あるとき、元の順序が保たれるソートを安定（stable）という。例えば名前順の名簿を点数順に並べ直したとき、同点の「50点の佐藤さん」と「50点の田中さん」が名前順のまま残るかどうか。隣同士しか交換しないバブルと挿入は安定、遠くの要素と一気に交換する選択ソートは（単純な実装では）不安定。

3. 競走させてみる — O(n²) の壁と、初期状態という個性

前章「計算量とO記法」の物差しで測ると、3つはどれも O(n²)。n個の要素に対して、比較回数はおよそ「全ペアの数」に比例するからです。

比較回数 ≈ n(n−1)/2 → O(n²) n=32 なら約500回、n=1,000 なら約50万回、n=100万 なら約5,000億回 — nが10倍になると手間は約100倍

ただし「同じO(n²)」でも個性は別物。同じ配列を3方式に同時スタートさせて確かめましょう。初期状態を「ほぼ整列済み」に切り替えると、順位が劇的に入れ替わります。

ソート競走 — 同じ配列で3方式を同時スタート
「手」＝比較・交換などの基本操作1回。ほぼ整列に切り替えると挿入ソートが圧勝します（すでに正しい位置の札はひと目の比較で終わるから）。一方、選択ソートはどんな配列でも毎回律儀に全スキャンするので手数がほぼ変わりません。逆順ではどうなるかも試してみましょう。
注意 — 実務では標準ライブラリを使う 実際の開発でソートを自分で書くことはまずない。各言語の標準ライブラリの sort（TimSort や introsort など）は O(n log n) で、しかも「ほぼ整列済みなら速い」といった実データ向けの最適化まで組み込み済み。この章の目的は、中身の動きと計算量の感覚を体で覚えることにある。

4. まとめ

一歩先へ — O(n log n) の世界 100万件を O(n²) でソートすると数千億回の操作が必要だが、マージソートやクイックソートなら約2,000万回で済む。鍵は「半分に割って別々に解く」分割統治という発想。第5章「高速なソート」で、この壁を越える瞬間を見に行こう。