選択ソート (Selection Sort)

未整列区間の最小値を探して先頭と交換する選択ソートを棒アニメーションで確認。交換がn−1回だけという特徴をカウンタで比較できます。

アルゴリズム

配列

サイズ48
比較中交換/書込ピボット/基準読み整列確定
速度50×

比較

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回のみ — 比較ソート中最少の書き込み回数です。不安定ソートです。 ソート可視化

よくある質問

選択ソートの利点は?
書き込み(交換)がn−1回しかない点です。フラッシュメモリ等、書込コストが高い環境で有利になり得ます。
安定ソートですか?
いいえ。最小値との交換で同値の順序が崩れることがあります。

他のアルゴリズム