選択ソート
最終更新
選択ソートは配列を左側のソート済み領域と右側の未ソート領域に分けます。各パスで未ソート領域を走査して最小の要素を見つけ、それを最初の未ソート位置に交換し、ソート済み領域を1つ広げます。上の再生を押して走査と交換の様子を見るか、比較を1つずつステップ実行してください。
選択ソートは入力に関係なく常に同じ回数の比較を行いますが、交換は最大でも n-1 回にとどまります。これはバブルソートよりはるかに少なく、書き込みのコストが高い場合に効いてきます。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良の場合 | O(n²) | ソート済みでも比較は行われる |
| 平均の場合 | O(n²) | ランダムな順序 |
| 最悪の場合 | O(n²) | 逆順 |
| 空間 | O(1) | インプレース |
| 安定 | いいえ | 交換により等しい要素の順序が入れ替わることがある |
ステップごとの流れ
| ステップ | 何が起こるか |
|---|---|
| 1 | 配列全体を未ソートとして扱う。 |
| 2 | 未ソート領域を走査して最小の要素を見つける。 |
| 3 | その最小値を最初の未ソート位置に交換する。 |
| 4 | 境界を1つ右へ移動する（その位置は以降ソート済み）。 |
| 5 | 未ソートの要素が1つになるまで繰り返す。 |
具体例
[5, 2, 4, 1] をソートする場合：
| パス | 配列 | 操作 |
|---|---|---|
| 開始 | [5, 2, 4, 1] | 配列全体が未ソート。 |
| 1 | [1, 2, 4, 5] | [5, 2, 4, 1] を走査し、最小はインデックス3の 1。インデックス0と交換する。 |
| 2 | [1, 2, 4, 5] | [2, 4, 5] を走査し、最小はすでにインデックス1にある 2。自分自身と交換する。 |
| 3 | [1, 2, 4, 5] | [4, 5] を走査し、最小はすでにインデックス2にある 4。移動は不要。 |
| 完了 | [1, 2, 4, 5] | 残るのは 5 のみで、すでに正しい位置にある。 |
選択ソートを使うべき場面
| 向いている場面 | 避けるべき場面 |
|---|---|
書き込みのコストが高い場合 - 交換は最大でも n-1 回。 | 配列が大きい場合 - O(n²) の比較が支配的になる。 |
| シンプルで実装しやすいインプレースのソートが必要な場合。 | 等しいキーの順序を保つ安定なソートが必要な場合。 |
メモリが逼迫している場合 - 追加領域は O(1) のみ。 | データがほぼソート済みの場合 - 挿入ソートのように早期終了できない。 |
| データセットが小さく、予測可能な性能が重要な場合。 | スループットが重要な場合 - クイックソートなど O(n log n) のソートの方がはるかに速い。 |
Selection Sortのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なSelection Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのSelection Sortのコード
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)JavaScriptでのSelection Sortのコード
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));JavaでのSelection Sortのコード
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}C++でのSelection Sortのコード
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}CでのSelection Sortのコード
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}選択ソートに関するよくある質問
選択ソートの時間計算量は？
選択ソートは最良・平均・最悪のいずれの場合でも
O(n²) です。各最小値を見つけるために常に未ソート領域全体を走査するためです。追加領域は O(1) を使用します。選択ソートは安定ですか？
標準的なインプレース版は安定ではありません。遠くの最小値を所定の位置に交換すると、等しい要素が別の要素を追い越すことがあるためです。安定な変種も存在しますが、交換ではなくシフトが必要です。
選択ソートはどんなときに役立ちますか？
メモリへの書き込みコストが高いときに役立ちます。交換は最大でも
n-1 回で、要素を移動する比較ソートとして可能な最小回数だからです。選択ソートとバブルソートの違いは？
どちらも
O(n²) の比較ソートですが、選択ソートの交換は最大 n-1 回であるのに対し、バブルソートは最大 O(n²) 回の交換を行うことがあります。またバブルソートはソート済みの配列を検出して早期に停止できますが、選択ソートは常にすべてのパスを実行します。選択ソートと挿入ソートのどちらを使うべき？
ほとんどの場合は挿入ソートが好ましいです。安定で、ほぼソート済みのデータでは
O(n) で動作し、平均的に高速だからです。選択ソートは、書き込み回数の最小化が最優先の場合にのみ選んでください。最大でも n-1 回の交換を保証するためです。なぜ選択ソートはソート済みの配列でも常に O(n²) で動くのですか？
選択ソートは、未ソート領域の残りを走査しない限りある要素がすでに最小かどうかを知る術がないため、入力の並びに関係なく各パスですべての比較を行います。そのため最良の場合が最悪の場合と同じ
O(n²) になります。早期に打ち切れる挿入ソートやバブルソートとは異なります。関連リソース
その他の可視化
