アルゴリズム・データ構造図鑑 · 基礎から応用へ

選択ソート:最小値の選択と交換の費用を分ける

未整列部分を走査して最小値を置く手順から、入力順に依存しない比較数と安定性を考える。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 各位置に置く値を確定する
  2. 3a、3b、1で安定性を確かめる
  3. 整列済みでも比較を省けない
  4. 使う条件を限定する
  5. この記事をロゲイアに質問する理解を確かめる

各位置に置く値を確定する

選択ソートは位置i以降から最小の要素を探し、その要素と位置iの要素を交換します。iより左側には全体で小さい方からi個の要素が並び、以降の反復では動かしません。一回の走査で保持するのは最小候補の位置だけであり、候補を見つけるたびに交換する必要はありません。挿入ソートのように整列済み部分へ要素を差し込む方法とは異なります。選ぶ操作と実際の交換を分けると、レコードの移動回数を正しく数えられます。

3a、3b、1で安定性を確かめる

同じキー3のレコードをaとbで区別した[3a,3b,1]を考えます。最小値1を先頭と交換すると[1,3b,3a]になり、3の出現順が逆転します。比較中に等しい候補を選び直していなくても、遠く離れた位置の交換で順序が崩れるのです。標準的な交換版は安定ではありません。最小値を取り出して中間をずらす安定版も作れますが、その場合は交換回数が少ないという標準版の特徴と、要素移動の費用を改めて評価する必要があります。

整列済みでも比較を省けない

n要素の標準版は、n−1、n−2、最後は1回の比較を行うため、合計はn(n−1)/2回です。既に整列していても残りの部分に小さい値がないことを走査で確かめるので、比較回数はほぼ変わりません。一方、自己交換を省けば実際の交換は高々n−1回です。時間計算量は定数時間比較の下でO(n²)、追加領域はO(1)です。比較が高価な場合とレコードの書き換えが高価な場合では、同じ二次時間の整列法でも評価が異なります。

使う条件を限定する

小さい配列で処理を単純に保ちたい場合や、比較よりも書き換えの回数を強く抑えたい場合に、選択ソートの特徴が役立つことがあります。ただし交換一回も実際には複数回の代入を伴い、間接参照やキャッシュの費用まで一定とは限りません。ほぼ整列した入力の速さを求めるなら、挿入ソートのような適応性はありません。空配列、同値キー、逆順入力で結果と比較数を検証し、安定性が仕様に含まれるなら標準版をそのまま選ばないようにします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ