3-9. 選択法による昇順整列のアルゴリズム

2025年2月19日 21:19

　本記事では、選択法による昇順整列のアルゴリズムに関する問題演習をします。

問題　配列中から最小値を求める方法を使って、選択法によって昇順に整列するアルゴリズムを作成してください。なお、選択した最小値を対象範囲の先頭に入れることになるが、このとき、先頭の位置にあった値がなくならないように注意してください。つまり、対象範囲における先頭の値と最小値を、交換しながら整列を進めるため、最小値の値と位置をそれぞれ変数に求めておくアルゴリズムにする必要があります。

解答

i ← 1
while (i ＜データ数） // 右端の前まで位置が確定すれば整列完了
　w ← A[ i ] // 最小値の候補（初期値）
　k ← i // 候補の位置
　j ← i + 1 // 左端の次から比較を始める
　while (j ≦ データ数） // 右端まで比較する
　　if ( A[i] ＜ w)　// 候補より小さい値?
　　　w ← A[ j ] // 最小値の候補
　　　k ← j // 候補の位置
　　endif
　　j ← j + 1 // 次の比較を行う
　endwhile
　A[k] ← A[i] // 左端の値を最小値の位置に
　A[i] ← w // 左端に最小値を
　i ← i + 1 // 左端を一つ右に
endwhile

　最小値を選択するアルゴリズムでは、まず、範囲の左端の要素を最小値の候補として、変数に入れておきます。この変数と左端の次から右端までの各データと比較していきます。このとき、変数の値よりも小さいものがあれば、その値が最小値の候補となりますから、変数にその値を入れます。そして、右端までの比較が終わった段階で最終的に変数に入っている値が最小値であるというものです。最小値の選択では、最小値の値だけが求められれば良かったのですが、これを選択法で利用する場合、範囲の左端と子の最小値を入れ替えることになるので、最小値がどの要素なのか、つまり、その要素位置もわからなければならないことに注意しましょう。

補足

選択ソート（Selection Sort）の解説

　選択ソートは、配列の中から最小値を見つけ、それを現在の位置と交換しながらソートを進めるアルゴリズムです。

アルゴリズムの流れ

対象範囲の左端の値を最小値の候補（w）として記録
左端の次（j）から右端まで比較し、より小さい値があれば最小値の候補を更新
最小値の位置（k）を記録
最小値（A[k]）と現在の左端（A[i]）を交換
左端を1つ右に移動し、次の探索を行う
これをデータの右端の1つ手前まで繰り返す

Javaでの実装

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] A) {
        int n = A.length;
        for (int i = 0; i < n - 1; i++) {  // 左端の位置を決定
            int w = A[i];  // 最小値の候補（初期値）
            int k = i;     // 候補の位置

            for (int j = i + 1; j < n; j++) {  // 右端まで比較
                if (A[j] < w) {  // より小さい値が見つかったら
                    w = A[j];  // 新しい最小値の候補
                    k = j;     // その位置を記録
                }
            }

            // 最小値（A[k]）と左端（A[i]）を交換
            A[k] = A[i];
            A[i] = w;
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13};
        System.out.println("ソート前: " + Arrays.toString(data));

        selectionSort(data);

        System.out.println("ソート後: " + Arrays.toString(data));
    }
}

Pythonでの実装

def selection_sort(A):
    n = len(A)
    for i in range(n - 1):  # 左端の位置を決定
        w = A[i]  # 最小値の候補（初期値）
        k = i     # 候補の位置

        for j in range(i + 1, n):  # 右端まで比較
            if A[j] < w:  # より小さい値が見つかったら
                w = A[j]  # 新しい最小値の候補
                k = j     # その位置を記録

        # 最小値（A[k]）と左端（A[i]）を交換
        A[k], A[i] = A[i], w

# 実行例
data = [29, 10, 14, 37, 13]
print("ソート前:", data)

selection_sort(data)

print("ソート後:", data)

解説

iの役割
- i はソートの基準となるインデックスで、左端の位置を示す。
- i を 0 から n-1 まで増やしながら、順番に最小値を確定させる。
wの役割
- w は最小値の候補として、最初に A[i] をセット。
- j でループを回しながら、w より小さい値を見つけたら w を更新。
kの役割
- k は最小値の位置を記録し、後で交換するときに使用する。
j の役割
- j = i + 1 から始めて、A[i] より右側のすべての値をチェックする。
交換の処理
- A[k] = A[i]（最小値の位置に、左端の値を入れる）
- A[i] = w（左端に最小値を入れる）

計算量

時間計算量: O(n²)
- 外側のループ (i のループ) が O(n)
- 内側のループ (j のループ) も O(n)
- 合計 O(n²) の計算量
空間計算量: O(1)
- 配列をその場でソートするため、追加のメモリは不要

まとめ

選択ソートは 単純なアルゴリズム で実装が容易
安定なソートではない（同じ値の要素の順序が保持されない）
計算量が O(n²) なので、大きなデータには向かない
配列内の交換回数が少ないため、書き換えのコストが低い場合に有利

以上です。