選択ソート

7.1 選択ソートの定義

選択ソート (Selection Sort) は、未ソートの配列部分から最小の要素を見つけ、それをこの部分の最初の要素と交換するアルゴリズムだよ。このプロセスを配列全体がソートされるまで繰り返すんだ。

動作原理:

1. 配列の最初の要素から始める。
2. 未ソート部分の配列から最小の要素を見つける。
3. 最小の要素と未ソート部分の最初の要素を交換する。
4. 次の要素についてこのプロセスを繰り返し、配列全体がソートされるまで続ける。

ステップバイステッププロセス

1. 配列の最小の要素を見つけて、最初の要素と交換する。
2. （2番目の要素から）残りの配列に対してプロセスを繰り返す。
3. 配列全体がソートされるまでプロセスを続ける。

選択ソートの時間と空間の複雑性

時間の複雑性:

• 最悪の場合: O(n^2) — 要素が最初から逆順またはランダムに並んでいる場合に発生する。
• 平均の場合: O(n^2) — 要素がランダムに配置されている場合。
• 最良の場合: O(n^2) — 配列がすでにソートされている場合でも、アルゴリズムは同じ比較を実行する。

空間の複雑性:

O(1) — アルゴリズムは一定の追加メモリ（いくつかの一時的変数だけを保持する）を使用するだけだからね。

7.2 選択ソートアルゴリズムの実装

アルゴリズムの実装は非常に簡単だよ:

ステップ 1: すべての要素の中で最小の要素を見つけて、最初の要素と交換する。

ステップ 2: 最初の要素以外のすべての要素の中で最小の要素を見つけて、2番目の要素と交換する。

ステップ 3: 最初と2番目以外のすべての要素の中で最小の要素を見つけて、3番目の要素と交換する。

Pythonでの実装例:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 残りの未ソート部分の配列から最小の要素を見つける
        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  # ソートされた配列を返す

# 使用例:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("ソートされた配列:", sorted_arr)
# 出力: ソートされた配列: [11, 12, 22, 25, 64]

アルゴリズムの動作例:

1. 最初の通過 (i = 0):
   1. 未ソート部分の配列 [64, 25, 12, 22, 11] から最小の要素 (11) を見つける。
   2. 11と64を交換する。
   3. 配列: [11, 25, 12, 22, 64]
2. 2番目の通過 (i = 1):
   1. 未ソート部分の配列 [25, 12, 22, 64] から最小の要素 (12) を見つける。
   2. 12と25を交換する。
   3. 配列: [11, 12, 25, 22, 64]
3. 3番目の通過 (i = 2):
   1. 未ソート部分の配列 [25, 22, 64] から最小の要素 (22) を見つける。
   2. 22と25を交換する。
   3. 配列: [11, 12, 22, 25, 64]
4. 4番目の通過 (i = 3):
   1. 未ソート部分の配列 [25, 64] から最小の要素 (25) を見つける。
   2. 25はすでにその場所にあるので、交換は不要。
   3. 配列: [11, 12, 22, 25, 64]

アルゴリズムは、すべての要素がソートされたので終了します。