選択ソートの仕組みを徹底解説！アニメーションで学ぶ「一番を探す」ソート【ソートアルゴリズム入門】#1

選択ソートをインタラクティブなツールも駆使しながら初心者・初学者向けにわかりやすく紹介します。

単純ソート３種のうちの一つ”単純選択ソート”

ソートアルゴリズムのうち、単純な並び替えでソート(並び替え)を行うものとして、挿入ソート・バブルソート・選択ソートがあり、これらを単純ソートと呼びます。

選択ソートの実行例　アニメーション

（※このほかにも、比較的低性能なソートを単純ソートと呼ぶ場合がある)

選択ソートは、その名の通り「未整列のデータ群から、最大値（または最小値）を選択 (Select) し、正しい位置（今回は末尾）に配置する」を繰り返す、非常に直感的なアルゴリズムです。

今回は、未ソート領域から「最大値」を見つけて配列の後ろから確定させていく「最大値選択法」を、自動探索アニメーション付きのツールで学んでいきましょう。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

1. 選択ソート（最大値選択法・単純選択法）とは？

選択ソート（最大値選択法）は、以下のステップを繰り返すアルゴリズムです。

まず、配列全体（未ソート領域）の中から一番大きな値（最大値）を探し出します。
見つけた最大値を、未ソート領域の一番後ろ（末尾）の要素と交換 (Swap) します。
これで、配列の一番後ろの要素は「確定（ソート済み）」となります。
次に、残りの「未ソート領域」（配列の先頭から末尾-1まで）に対して、再び 1. と 2. を繰り返します。
未ソート領域が1つになるまでこれを続けると、全体が整列されます。

2. 選択ソートでトランプを並び替えたら？

一番初めは、全体のうちの最大値を探す（選択）．

最大値が見つかったので、一番右と入れ替える

Kは最大で確定したので、Kを除く未ソート部分(Qから2まで）の最大値を探す（選択）．

３回目も同様にして、未ソート部分から最大値を見つけて選択し、入れ替える。

４枚目以降も同様にして、最後まで入れ替えたら完了。

3. 選択ソートの動きを見てみよう！

選択ソートで並び替えを試せます。ステップ実行ボタンを押して、並び替えを進めてみてください。

黄色が未ソート部分での最大値で、オレンジになっているところはすでに並び替え終わっています。

「再配置」を押して開始してください

選択ソートの疑似コード(ソートの手順)

手元で試せる環境があったら自身の慣れているプログラミング言語で以下の処理を書いてみると理解が深まると思います。

algorithm SelectionSort(L) is
  n ← length of L
  
  // i: 未ソート領域の末尾インデックス。
  // (n-1 から 1 まで、1ずつ減らす)
  for i from n-1 down to 1 do
    
    // --- 未ソート領域 (L[0]...L[i]) から最大値のインデックスを探す ---
    max_index ← 0 // ひとまず先頭を最大値とする
    
    // j: 探索インデックス (1 から i まで)
    for j from 1 to i do
      if L[max_index] < L[j] then
        max_index ← j // より大きい値が見つかったら、場所を更新
      end
    end
    
    // --- 最大値 (L[max_index]) と未ソート領域の末尾 (L[i]) を交換 ---
    temp ← L[max_index]
    L[max_index] ← L[i]
    L[i] ← temp
    
  end
  
  return L
end