選択ソートアルゴリズムの解説
選択ソートとは？
選択ソートは、ソートの中でも比較的単純なアルゴリズムです。配列の中で最も小さな要素を選び、それを先頭の要素と入れ替えます。この操作を繰り返し、リスト全体がソートされるまで続けます。
選択ソートのステップ
- 配列の中で最小の要素を探します。
- 見つけた最小の要素を、配列の先頭の要素と入れ替えます。
- 次に、残りの要素から同様の手順を繰り返します。
- すべての要素がソートされるまで、この操作を続けます。
選択ソートのステップごとの変化
| ステップ | リストの状態 | 交換された要素 |
|---|---|---|
| 初期状態 | [5, 2, 9, 1, 5, 6] | — |
| 1 | [1, 2, 9, 5, 5, 6] | 5, 1 |
| 2 | [1, 2, 9, 5, 5, 6] | — |
| 3 | [1, 2, 5, 9, 5, 6] | 9, 5 |
| 4 | [1, 2, 5, 5, 9, 6] | 9, 5 |
| 5 | [1, 2, 5, 5, 6, 9] | 9, 6 |
選択ソートはどのように動いているか
選択ソートのJavaScript実装
// 選択ソートのJavaScript実装
function selectionSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 最小値とi番目の要素を入れ替え
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
console.log(arr); // 途中経過を出力
}
return arr;
}
let array = [5, 2, 9, 1, 5, 6];
console.log("ソート前:", array);
console.log("ソート後:", selectionSort(array));
選択ソートのPython実装
# 選択ソートのPython実装
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# 最小値とi番目の要素を入れ替え
arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr) # 途中経過を出力
return arr
array = [5, 2, 9, 1, 5, 6]
print("ソート前:", array)
print("ソート後:", selection_sort(array))
まとめ
選択ソートはシンプルなソートアルゴリズムの一つで、特に学習目的には優れた例です。しかし、大きなデータセットに対しては効率が良くないため、他のアルゴリズムに比べてパフォーマンスが低下することがあります。実際に実装することで、その動作や限界を理解することが重要です。