ALDS1_2_B:

選択ソート

選択ソートでは、挿入ソート・バブルソートと同様に、各計算ステップにおいて、配列は「ソート済みの部分列」と「未ソートの部分列」とに分けられます。

以下の処理を $N-1$ 回繰り返す：

1. 未ソートの部分から最小の要素の位置 minj を特定する。
2. minj の位置にある要素と未ソートの部分の先頭要素を交換する。

例えば配列$\{5, 4, 8, 7, 9, 3, 1\}$に対して選択ソートを行うと次のようになります。

0. の初期状態では全ての要素が未ソートの部分に属します。
1. では、未ソートの部分列から最小値の位置を探し(minj = 6)、その位置の要素A [6] (= 1) と未ソートの部分列の先頭の要素 A[0] (= 5) を交換します。ソート済みの要素が１つ増えます。
2. では、未ソートの部分列から最小値の位置を探し(minj = 5)、その位置の要素 A[5] (= 3) と未ソートの部分列の先頭の要素 A[1] (= 4) を交換します。以下同様に繰り返し、配列の先頭から小さい順に値が決定していきます。

選択ソートの実装に必要な主な変数は以下のようになります。

各i のループで j をi から N-1 まで調べて minj を決定します。minj が決定した後、先頭要素A[i] と最小値 A[minj] を交換します。

選択ソートの計算量を考えてみましょう。データの数をNとすると、選択ソートは未ソートの部分の最小値を見つけるために $N-1$ 回、$N-2$ 回、$N-3$ 回、$... 1$ 回の比較演算を行います。よって合計の比較演算の回数は常に $(N^2-N)/2$ となることから、選択ソートの計算量は $N^2$ に比例し、オーダーが $O(N^2)$ のアルゴリズムとなります。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。