未整列区間の最小値を探して先頭と交換する選択ソートを棒アニメーションで確認。交換がn−1回だけという特徴をカウンタで比較できます。
アルゴリズム
配列
比較
0
交換/書込
0
ステップ
0/1,577
読み
0
補助メモリ
0
再帰の深さ
1/1
速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。
疑似コード
for i ← 0 to n−1
min ← i
for j ← i+1 to n−1
if a[j] < a[min]
min ← j
swap a[i] ↔ a[min]
計算量
| 最良 | O(n²) |
|---|---|
| 平均 | O(n²) |
| 最悪 | O(n²) |
| 空間 | O(1) |
| 安定 | × |
選択ソートは未整列区間から最小値を探し(選択)、その区間の先頭要素と交換するアルゴリズムです。紫の棒が現在の最小値位置で、前から1つずつ確定していきます。
比較は常にn(n−1)/2回で全ケースO(n²)ですが、交換はn−1回のみ — 比較ソート中最少の書き込み回数です。不安定ソートです。 ソート可視化