選択ソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
選択ソート
Selection Sort Animation
クラス ソート
データ構造 配列
最悪計算時間 О(n²)
最良計算時間 О(n²)
平均計算時間 О(n²)
最悪空間計算量 О(n) total, O(1) auxiliary

選択ソート: selection sort)は、ソートアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、非常に直感的で単純なアルゴリズムであり、実装も容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。

このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

アルゴリズム[編集]

データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す(厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後(残り)は必ず最大値になるからである)。大小が入れ替わる降順の場合も同様の手法である。また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、double selection sortと呼ばれる。

実装例[編集]

for I := 1 to N
  min := I
  for J := I+1 to N  
    if data[J] < data[min] then
      min := J
    end if
  end for
  swap(data[I], data[min])
end for

Pythonでの実装例[編集]

#非破壊操作
def selectionSort(data):
    ret = []
    for i in range(len(data)):
        pos = 0
        for j in range(1, len(data)):
            if data[j] < data[pos]:
                pos = j
        ret.append(data[pos])
        data = data[:pos] + data[pos+1:]
    return ret

#破壊操作
def min_index(i, x):
    min = i
    for j in range(len(x[i:])):
        if x[i+j] < x[min]:
            min = i+j
    return min

def swap(i, j, x):
    tmp = x[i]
    x[i] = x[j]
    x[j] = tmp

def selection_sort(x):
    for i in range(len(x)):
        min = min_index(i, x)
        swap(i, min, x)
    return x

Pythonでの実装例(別解)[編集]

def selectionSort(lst):
    acc = []
    while True:
        if lst == []:
            return acc
        else:
            x = min(lst)
            acc.append(x)
            lst = [i for i in lst if i != x]

C#での実装例[編集]

using System;

namespace SelectionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int temp,min;
            Console.WriteLine("選択ソート実装例");
            Console.Write("ソートしたいデータ数を入力ください :  ");
            int dataNumber = Convert.ToInt32(Console.ReadLine());
            int[] array = new int[dataNumber];
            Console.WriteLine("\n");

            for (int i = 0; i < dataNumber; i++)
            {
                Console.Write("[" + (i + 1) + "]番目のデータを入力してください :  ");
                array[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine("\n");
            foreach (int a in array)
                Console.Write(a + " ");

            for(int i = 0; i < array.Length; i++)
            {
                min = i;
                for(int j = i + 1; j < array.Length; j++)
                {
                    if(array[j] < array[min])
                    {
                        min = j;
                    }
                }
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
            Console.WriteLine("\n");
            Console.WriteLine("ソートされた結果 : ");
            foreach (int n in array)
                Console.Write(n + " ");
            Console.ReadKey();
        }
    }
}
Selection-Sort-Animation

Schemeでの実装例[編集]

(require-extension srfi-1)              ; 実装依存。SRFI-1 と言うライブラリを用いる。

(define (selection-sort ls)
  (let loop ((ls ls) (acc '()))
    (if (null? ls)
        (reverse acc)
        (let ((x (apply min ls)))
          (loop (remove (lambda (y)
                          (= y x)) ls) (cons x acc))))))

動作例[編集]

初期データ: 8 4 3 7 6 5 2 1 

太字はソート完了した部分

1 4 3 7 6 5 2 8 (1回目のループ終了時)
1 2 3 7 6 5 4 8 (2回目のループ終了時)
1 2 3 7 6 5 4 8 (3回目のループ終了時)
1 2 3 4 6 5 7 8 (4回目のループ終了時)
1 2 3 4 5 6 7 8 (5回目のループ終了時)
この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。
1 2 3 4 5 6 7 8 (6回目のループ終了時)
1 2 3 4 5 6 7 8 (7回目のループ終了時)


計算時間[編集]

「比較回数」は、n(n-1)/2回。「交換回数」は、各ループで最大1回なので、全体では多くともn-1回。バブルソートと比較すると、「比較回数」は同じだが「交換回数」が少ないので、選択ソートの方が高速である。

安定性[編集]

初期データ: 2a 3 2b 1 とすると、

1 3 2b 2a (1回目のループ終了時)
1 2b 3 2a (2回目のループ終了時)
1 2b 2a 3 (3回目のループ終了時)

となり、2a, 2bの前後関係が初期データの状態から維持されていない。よって安定ソートではない。