選択ソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、単純な整列アルゴリズムである選択ソート（Selection Sort）について学んでいきます。

選択ソートとは
Pythonで選択ソートを実装してみる
動作確認
参考書籍

選択ソートとは

選択ソート（Selection Sort）とは、リストの先頭と2番目～最後までの中で最小の値を探し、リストの先頭と交換します。

最小の値はリストの先頭に格納されたので、次はリストの2番目と3番目～最後までの中で最小の値を探し、、、といった処理を繰り返します。

前回のバブルソートと同様に外側と内側のループを使用したスキャンになるため、計算量は $O(n^2)$ となりますが、交換のコストがバブルソートよりもかからないため、負荷は少ないです。

なお、選択ソートは安定な整列アルゴリズム（データの位置関係が保存される）ではありません。

Pythonで選択ソートを実装してみる

それでは、Pythonで選択ソートを実装してみます。

# selection_sort.py
import time
import pickle

def selection_sort(lst):
    length = len(lst)
    for i in range(length-1):
        lowest = i
        lowkey = lst[i]
        for j in range(i+1, length):
            if lst[j] < lowkey:
                lowest = j
                lowkey = lst[j]
        tmp = lst[i]
        lst[i] = lst[lowest]
        lst[lowest] = tmp

with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

start = time.time()
selection_sort(lst)
print("elapsed {} sec".format(time.time() - start))