[Python] 選択ソートの実装方法とアルゴリズム

Pythonと選択ソート

Pythonで選択ソートを実装してみます。Python3.6を使います。選択ソートはバブルソートに次いで、単純で理解しやすいソートアルゴリズムです。

# 選択ソート
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
        # 見つけた最小値を未整列末尾要素と交換
        tmp = array[min]
        array[min] = array[i]
        array[i] = tmp

# デバッグ
if __name__ == "__main__":
    array = [1,2,3,4,5,3,2,1,4,3,4,5,0]
    print("before", array)
    selection_sort(array)
    print("after ", array)

選択ソートのアルゴリズム

選択ソートは未整列部分から最小値(最大値)を選択し、整列済部分の末尾要素と交換します。比較ソートの一種で、バブルソートと同じく比較交換を繰り返しますが、交換回数が少なく済むためやや処理速度の面で優秀です。それでも時間計算量 O(n^2) で遅いのですが。

参考URL

• 選択ソート – Algoful
• 選択ソート – Wikipedia