アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

選択ソートとは

選択ソートとは、対象データから最小値(最大値)を選択・交換を繰り返すことでソートを行います。

隣り合う要素を交換するバブルソートと比較し、最小値(最大値)の交換を繰り返す選択ソートは、データの交換回数一定して少なくなります。よってバブルソートよりは高速になります。

選択ソートは 安定 な 内部 ソートです。計算量は O(n²) で処理速度は低速です。

選択ソートのシミュレーション

背景色が黄色のタイミングで比較が実行されています。ソート済のデータは水色になります。未整列のデータの中から最小値を見つけて交換しているのがわかります。

アルゴリズムの解説

「未整列の要素の中から最小値(最大値)を探し出し、ソート済の要素の後ろの要素と交換」 これを n-1回繰り返します。するとソート済のデータが得られます。

サンプルコード

C#

public static void SelectionSort<T>(T[] array) where T : IComparable<T>
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int min = i;    // 最小値のインデックス保持用
        // このループが終われば min には最小値のインデックスが入っている
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[min].CompareTo(array[j]) > 0)
            {
                min = j;
            }
        }
        // 見つかった最小値の値を交換
        Swap(ref array[min], ref array[i]);
    }
}

public static void Swap<T>(ref T a, ref T b)
{
    var tmp = a;
    a = b;
    b = tmp;
}

Python

def selection_sort(array):
    n = len(array)
    for i in range(0, n-1):
        min = i
        for j in range(i+1, n):
            if array[min] > array[j]:
                min = j
        else:
            tmp = array[min]
            array[min] = array[i]
            array[i] = tmp