- 比較中
- 現在の最小値
- 交換済み
- 確定
選択ソート
選択ソートは、整列済みのリストを先頭から作っていきます。各パスでまだ整列していない値を走査し、その中の最小値を覚えておいて、未整列部分の先頭と交換します。好きな速度で再生するか、比較を1回ずつ進めて、比較回数、交換回数、パス数のカウンターを見てみましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、交換回数、パス数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
- 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
- 走査が進むにつれて現在の最小値が変わる様子と、各パスの最後にそれを確定位置へ移す交換を見てみましょう。
選択ソートの仕組み
リストのすべての値を見て、最小値を覚えておきます。それを先頭の値と交換すると、先頭の位置が確定します。次に、1つ後ろの位置から残りのリストで同じことをします。n − 1回のパスですべての値が確定し、最後の1つは自然に正しい位置に残ります。
比較は多く、交換は少ない
走査が途中で止まることはありません。残りの値をすべて見て初めて、どれが最小か確かめられるからです。そのため選択ソートは、リストが整列済みでも逆順でもランダムでも、n個の値に対してちょうどn(n − 1)/2回比較します。その代わり、交換は1パスにつき1回、最大でもn − 1回です。値の移動が2つの値の比較よりずっと高くつく場合には、悪くない選択です。
よくある質問
選択ソートはどのように動きますか?
まだ整列していない最小値を選び、未整列部分の先頭と交換することを繰り返します。k回目のパスの後、最初のk個の位置には小さい方からk個の値が順に並びます。
選択ソートの比較回数と交換回数は?
n個の値に対して比較は常にn(n − 1)/2回です。10個なら45回、40個なら780回です。交換は1パスにつき1回で最大n − 1回、最小値がすでに確定位置にあればそれより少なくなります。
整列済みのリストが逆順のリストと同じだけ時間がかかるのはなぜですか?
各パスで最小値を見つけたと確かめるには、残りの値をすべて見る必要があるからです。バブルソートや挿入ソートと違い、選択ソートは比較の結果からリストが整列済みだと判断できません。
選択ソートは安定ですか?
一般的な形では安定ではありません。交換によって、ある値が等しい値を追い越すことがあります。2, 2, 1 では最初の2が1と交換され、2つ目の2の後ろに来ます。交換の代わりに値をずらす版は安定ですが、移動が増えます。
入力した数値はどこかに送信されますか?
いいえ。並べ替えはブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ