【ITニュース解説】Selection Sort: Detailed Explanation

セレクションソートは、データを指定した順序（例えば小さい順）に並べ替えるための基本的なアルゴリズムの一つだ。これは、配列の要素を互いに比較しながら並べ替える「比較ソート」という種類に属する。その主な特徴は、考え方が非常にシンプルで、プログラムとして実装しやすい点にある。しかし、大量のデータをソートする場合には、あまり効率的ではないという弱点も持ち合わせている。

このソートアルゴリズムの基本的な考え方は、配列の中から最も小さい（または最も大きい）要素を繰り返し探し出し、それをまだ整列されていない部分の先頭、つまり最終的にあるべき正しい位置に移動させることだ。この操作を、配列全体が完全に整列されるまで続けていく。

具体的なアルゴリズムのステップを見ていこう。まず、配列の先頭から処理を開始する。最初の要素を、現時点での最小値であると仮定し、その要素のインデックス（配列内の位置）をminIndexという変数に記録する。次に、この仮定した最小値の要素の隣から、配列の最後までにあるすべての要素と一つずつ比較していく。もし比較対象の要素が、現在minIndexが指している要素よりも小さければ、minIndexをその新しい最小値の要素のインデックスに更新する。

この比較処理を未整列部分の最後まで行うと、minIndexにはその未整列部分の中で最も小さい要素のインデックスが正確に記録されているはずだ。ここで、現在の処理位置（iで示される）にある要素と、minIndexが指す最も小さい要素を入れ替える（この操作を「スワップ」と呼ぶ）。このスワップによって、現在の処理位置iには、未整列部分から見つかった最小の要素が配置され、この位置の要素はもう動かす必要がない整列済み状態となる。

一つの位置の要素が確定したら、今度は次の位置へ移り、同じ手順を繰り返す。つまり、iの値を一つ増やし、残りの未整列部分に対して再び最小値の探索とスワップを行うのだ。この一連の作業を、配列の全要素が正しい位置に配置されるまで、つまり配列全体が整列されるまで繰り返していく。minIndexは、常に未整列部分の最小要素の位置を追跡し、スワップは各外側ループの繰り返しにつき一度だけ、内側ループが最小値を見つけ出した後に行われる。外側のループが、配列の各位置を正しい最小の要素で満たしていく役割を果たす。

セレクションソートの性能について見てみよう。時間計算量はO(n²)とされている。これは、配列の要素数（n）が増えると、処理時間がnの二乗に比例して増えることを意味する。例えば、要素が2倍になると処理時間は約4倍になる可能性があるため、大規模なデータには向かない。一方、空間計算量はO(1)だ。これは、ソートを行うために必要な追加のメモリ領域が、配列のサイズに関わらず一定であることを意味し、元の配列内で直接ソートを行う「インプレースソート」と呼ばれるタイプに分類される。

それでは、具体的な配列の例を使って、セレクションソートがどのように動作するかを段階的に見ていこう。以下の配列を昇順にソートする例を考える。 int[] arr = {13, 12, 11, 10, 9, 33, 12}

外側のループ: i = 0 （最初の位置） 配列の先頭、インデックス0から開始する。

• minIndexを0と設定する（要素は13）。
• 内側のループでj = 1から配列の最後までを比較していく。
  • j = 1：arr[1]の12とarr[minIndex]の13を比較。12 < 13なので、minIndexは1に更新される。
  • j = 2：arr[2]の11とarr[minIndex]の12を比較。11 < 12なので、minIndexは2に更新される。
  • j = 3：arr[3]の10とarr[minIndex]の11を比較。10 < 11なので、minIndexは3に更新される。
  • j = 4：arr[4]の9とarr[minIndex]の10を比較。9 < 10なので、minIndexは4に更新される。
  • j = 5：arr[5]の33とarr[minIndex]の9を比較。33 < 9は偽なので、minIndexは4のまま。
  • j = 6：arr[6]の12とarr[minIndex]の9を比較。12 < 9は偽なので、minIndexは4のまま。
• 内側のループが終了し、minIndexは4を指している。これは、未整列部分で最も小さい要素9がインデックス4にあることを意味する。
• arr[0]（13）とarr[4]（9）をスワップする。
• 配列は[9, 12, 11, 10, 13, 33, 12]となる。これで最初の位置0には最小値9が正しく配置された。

外側のループ: i = 1 （二番目の位置） 次に、インデックス1から処理を続ける。arr[0]は既にソート済みだ。

• minIndexを1と設定する（要素は12）。
• 内側のループでj = 2から配列の最後までを比較していく。
  • j = 2：arr[2]の11とarr[minIndex]の12を比較。11 < 12なので、minIndexは2に更新される。
  • j = 3：arr[3]の10とarr[minIndex]の11を比較。10 < 11なので、minIndexは3に更新される。
  • j = 4：arr[4]の13とarr[minIndex]の10を比較。13 < 10は偽なので、minIndexは3のまま。
  • j = 5：arr[5]の33とarr[minIndex]の10を比較。33 < 10は偽なので、minIndexは3のまま。
  • j = 6：arr[6]の12とarr[minIndex]の10を比較。12 < 10は偽なので、minIndexは3のまま。
• 内側のループが終了し、minIndexは3を指している（要素は10）。
• arr[1]（12）とarr[3]（10）をスワップする。
• 配列は[9, 10, 11, 12, 13, 33, 12]となる。位置1には10が正しく配置された。

外側のループ: i = 2 （三番目の位置） インデックス2から処理を続ける。arr[0]とarr[1]はソート済み。

• minIndexを2と設定する（要素は11）。
• 内側のループでj = 3から配列の最後までを比較していく。
  • j = 3：arr[3]の12とarr[minIndex]の11を比較。12 < 11は偽なので、minIndexは2のまま。
  • j = 4：arr[4]の13とarr[minIndex]の11を比較。13 < 11は偽なので、minIndexは2のまま。
  • j = 5：arr[5]の33とarr[minIndex]の11を比較。33 < 11は偽なので、minIndexは2のまま。
  • j = 6：arr[6]の12とarr[minIndex]の11を比較。12 < 11は偽なので、minIndexは2のまま。
• 内側のループが終了し、minIndexは2を指している。minIndexと現在のiが同じ値なので、スワップは行われない。
• 配列は[9, 10, 11, 12, 13, 33, 12]のまま。位置2には11が元々正しく配置されていた。

外側のループ: i = 3 （四番目の位置） インデックス3から処理を続ける。arr[0]からarr[2]はソート済み。

• minIndexを3と設定する（要素は12）。
• 内側のループでj = 4から配列の最後までを比較していく。
  • j = 4：arr[4]の13とarr[minIndex]の12を比較。13 < 12は偽なので、minIndexは3のまま。
  • j = 5：arr[5]の33とarr[minIndex]の12を比較。33 < 12は偽なので、minIndexは3のまま。
  • j = 6：arr[6]の12とarr[minIndex]の12を比較。12 < 12は偽なので、minIndexは3のまま。
• 内側のループが終了し、minIndexは3を指している。minIndexと現在のiが同じなので、スワップは行われない。
• 配列は[9, 10, 11, 12, 13, 33, 12]のまま。位置3には12が元々正しく配置されていた。

外側のループ: i = 4 （五番目の位置） インデックス4から処理を続ける。arr[0]からarr[3]はソート済み。

• minIndexを4と設定する（要素は13）。
• 内側のループでj = 5から配列の最後までを比較していく。
  • j = 5：arr[5]の33とarr[minIndex]の13を比較。33 < 13は偽なので、minIndexは4のまま。
  • j = 6：arr[6]の12とarr[minIndex]の13を比較。12 < 13なので、minIndexは6に更新される。
• 内側のループが終了し、minIndexは6を指している（要素は12）。
• arr[4]（13）とarr[6]（12）をスワップする。
• 配列は[9, 10, 11, 12, 12, 33, 13]となる。位置4には12が正しく配置された。

外側のループ: i = 5 （六番目の位置） インデックス5から処理を続ける。arr[0]からarr[4]はソート済み。

• minIndexを5と設定する（要素は33）。
• 内側のループでj = 6から配列の最後までを比較していく。
  • j = 6：arr[6]の13とarr[minIndex]の33を比較。13 < 33なので、minIndexは6に更新される。
• 内側のループが終了し、minIndexは6を指している（要素は13）。
• arr[5]（33）とarr[6]（13）をスワップする。
• 配列は[9, 10, 11, 12, 12, 13, 33]となる。位置5には13が正しく配置された。

外側のループ: i = 6 （最後の位置） インデックス6から処理を続ける。この時点で、残りの未整列部分は要素一つだけなので、既に正しい位置にあると判断される。特に操作は行われない。

• 配列は[9, 10, 11, 12, 12, 13, 33]のまま。

これで、配列全体が[9, 10, 11, 12, 12, 13, 33]と完全に昇順にソートされた。

この詳細な例からわかるように、セレクションソートでは、minIndexが常に未整列部分の中で最小の要素のインデックスを正確に追跡している。内側のループは、残りのすべての要素を現在の最小値と比較し、より小さい値が見つかればminIndexを更新する。もしminIndexと現在のiが同じであれば、その位置の要素は既に正しい位置にあるため、無駄なスワップを避けることができる。各外側ループの繰り返しによって、その時点での最小の要素が配列の正しい位置に順々に配置されていき、最終的に配列全体が整列される仕組みだ。セレクションソートは、その単純なロジックから、ソートアルゴリズムの基本を学ぶ上で非常に適していると言える。