[ソート] 選択ソート

選択ソート

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

選択ソートは、配列を「ソート済み部分」と「未ソート部分」との2つに分け、「未ソート部分」で最小値/最大値の検索を行い、その結果を「ソート済み部分」に移動させることでソートを行います。

より具体的には、配列の中で最も小さい値を探して、その要素と先頭の要素と交換します。この時点で、先頭が「ソート済み部分」に、残りが「未ソート部分」になります。

次に、「未ソート部分」に該当する配列2番目以降のデータから一番小さい値を探して、2番目の要素と交換します。この時点で、先頭と2番目が「ソート済み部分」に、残りが「未ソート部分」になります。 …　これを、リストの最後まで繰り返すと、最終的に昇順にソートされます。

計算量はバブルソートと同じ\( O (N^2)\)ですが、選択ソートはバブルソートより高速です。

また、対象となる配列が小さい時はクイックソートよりも高速になるので、配列の要素数によるソート方法の使い分けが行われます。

同じ \( O (N^2)\) の計算量である挿入ソートと比較すると、選択ソートは配列への「書き込み」回数が挿入ソートより少ないので、特にフラッシュメモリのような書き込みコストの高いメモリを使う場合は有用になります。

内部ソートですが、安定ソートではありません。

Python で実装

選択ソートを Python で実装します。

import random

def selection_sort(array):
    for i in range(len(array)):
        least = i
        for k in range(i + 1 , len(array)):
            if array[k] < array[least]:
                least = k
        swap(array, least, i)
    return array

def swap(array, x, y):
    array[y], array[x] = array[x], array[y]



if __name__ == '__main__':
    # ランダムな配列の生成
    random.seed(1)
    array = [random.randrange(100) for i in range(10)]
    print('未ソート', array)
    # 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60]
    
    print('ソート済み', selection_sort(array)) 
    # ソート済み [8, 15, 17, 32, 57, 60, 63, 72, 97, 97]