選択ソート

選択ソートは、ソートアルゴリズムの一つで、配列から最小値（または最大値）を探し出し、それを配列の先頭要素と交換していくことで並べ替える手法です。このプロセスを未ソート部分がなくなるまで繰り返すことで、最終的に配列全体がソートされます。

アルゴリズムの詳細

選択ソートの基本的な手順は以下の通りです。

1. 配列の先頭から未ソート部分の中で最小値を持つ要素を探します。
2. 見つかった最小値の要素と未ソート部分の先頭要素を交換します。
3. 未ソート部分の範囲を一つ後ろにずらし、手順1と2を繰り返します。
4. 未ソート部分がなくなるまで、またはすべての要素がソートされるまでこの手順を続けます。

昇順にソートする場合は最小値を、降順にソートする場合は最大値を探索します。また、各ループで最小値と最大値の両方を探し、それぞれを配列の両端に配置する手法も存在し、これはdouble selection sortと呼ばれます。

擬似コード例

以下に選択ソートの擬似コードを示します。


for i = 0 to n-2
min_index = i
for j = i+1 to n-1
if array[j] < array[min_index]
min_index = j
swap array[i] and array[min_index]

動作例

初期データとして `8 4 3 7 6 5 2 1` を昇順にソートする例を以下に示します。太字はソート済みの部分を表します。

1 4 3 7 6 5 2 8 (1回目のループ終了時)
1 2 3 7 6 5 4 8 (2回目のループ終了時)
1 2 3 7 6 5 4 8 (3回目のループ終了時)
1 2 3 4 6 5 7 8 (4回目のループ終了時)
1 2 3 4 5 6 7 8 (5回目のループ終了時)
1 2 3 4 5 6 7 8 (6回目のループ終了時)
1 2 3 4 5 6 7 8 (7回目のループ終了時)

この例では、ソートが進むにつれて配列が整理されていく様子がわかります。しかし、アルゴリズムは配列全体を完全に処理する必要があります。

計算時間

選択ソートの計算量は、要素の比較回数と要素の交換回数で評価できます。

要素の比較: 配列の要素数を`n`とすると、各ループで `n-1`, `n-2`, ... , `1` 回の比較が行われます。したがって、比較回数の合計は `n(n-1)/2` となります。
要素の交換: 各ループで最大1回の交換が行われるため、最大で `n-1` 回の交換が行われます。

バブルソートと比較すると、選択ソートは比較回数は同じですが、交換回数が少ないため、一般的に高速です。

安定性

選択ソートは安定なソートアルゴリズムではありません。安定ソートとは、同じ値を持つ要素の相対的な順序がソート後も保持される性質を指します。選択ソートの場合、同値の要素の順序が入れ替わる可能性があるため、安定ではありません。

例えば、`2a 2b 1`という配列をソートする場合、選択ソートでは、

`2a 2b 1` (初期状態)
`1 2b 2a` (1回目のループ終了時)
`1 2b 2a` (2回目のループ終了時)
`1 2b 2a` (終了状態)

となり、`2a`と`2b`の順序が入れ替わっています。したがって、選択ソートは安定ではないことがわかります。

実装例

以下に、Python、C#、Schemeでの選択ソートの実装例を示します。

Python

python
def selection_sort(arr):
n = len(arr)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

C#

csharp
public static void SelectionSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
int minIdx = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIdx])
{
minIdx = j;
}
}
(arr[i], arr[minIdx]) = (arr[minIdx], arr[i]);
}
}

Scheme

scheme
(define (selection-sort lst)
(let ((len (length lst)))
(letrec ((sort-loop (lambda (i)
(if (< i (- len 1))
(let ((min-idx (letrec ((find-min (lambda (j current-min index)
(if (= j len)
(cons current-min index)
(if (< (list-ref lst j) current-min)
(find-min (+ j 1) (list-ref lst j) j)
(find-min (+ j 1) current-min index)))))
(find-min (+ i 1) (list-ref lst i) i))))
(min-val (car min-idx))
(min-index (cdr min-idx)))
(if (not (= i min-index))
(let ((temp (list-ref lst i)))
(set! lst (list-update lst i (list-ref lst min-index)))
(set! lst (list-update lst min-index temp)))))
(sort-loop (+ i 1))))))
(sort-loop 0))
lst))

(define (list-update lst index value) (if (= index 0) (cons value (cdr lst)) (cons (car lst) (list-update (cdr lst) (- index 1) value))))

まとめ

選択ソートは、実装が比較的簡単で理解しやすいアルゴリズムですが、時間計算量が大きいため、大規模なデータには向いていません。しかし、空間計算量が限られている状況や、ソートするデータ量が小さい場合には有効な選択肢となることがあります。より効率的なソートアルゴリズムが必要な場合は、クイックソートやマージソートなどを検討する必要があります。

もう一度検索