整列選択(Selection Sort)

特定のデータの最小値を検索し、先頭のデータを置換するソートアルゴリズム.
時間複雑度:O(N^2)

例

最初のデータ1は最小値にソートされました
先頭のデータは10で、最小値は2です.👉 swap
先頭のデータは5で、最小値は3です.👉 swap
先頭のデータは8で、最小値は4です.👉 swap
先頭のデータは7で、最小値は5です.👉 swap
先頭のデータは6で、最小値は6です.👉 あぶらがみ
先頭のデータは8で、最小値は7です.👉 swap
先頭のデータは8で、最小値は8です.👉 あぶらがみ
先頭のデータは10で、最小値は9です.👉 swap
先頭のデータは10で、最小値は10です.👉 あぶらがみ

インプリメンテーション

github link

def selection_sort(data):
    for i in range(len(data)):
        min_idx = i
        for j in range(i+1, len(data)):
            if (data[min_idx] > data[j]):
                min_idx = j
        data[i], data[min_idx] = data[min_idx], data[i]
    return data

if __name__ == "__main__":
    data = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
    res = selection_sort2(data)
    print('res: ', res)

重複データの数:
1つ目:0からnまでの最小値を検索し、データ[0]が大きい場合はdata[0]とswapを使用します.
2つ目:1からnの最小値を検索し、データ[1]がより大きい場合はdata[1]とswapを使用します.
(i-1)2つ目:i~nの最小値を検索し、データ[i]が大きい場合はdata[i]とswapを使用する
(2)データ長で循環する、
(3)最初に一番前のインデックスを最小要素のインデックスに設定
(4-6)一番前の要素を除いて、一番小さい数字を探します
(7)swap:C言語と異なり,Pythonは一時記憶変数を用いずに2つの変数の値を変更することができる.

int a = 3;
int b = 5;

int temp = a;
a = b;
b = temp;

C言語でswapを行うには、変数tempを一時的に格納する必要がある.

時間の複雑さ

N-1にソートし、最小の数を見つけて一番前に送信します.
最小の数を見つけるには、毎回比較演算が必要です.以上の実装コードに基づいて,計算回数はN+(N−1)+(N−2)+...+2と見ることができます.
近似値で表すとNx(N+1)/2であり,bigoマーキング法で簡単にO(N^2)と表すことができる.
ソースコードには二重for文が用いられているので,時間的複雑度はO(N^2)と考えられる.つまり、ソートするデータが100個ある場合、ソートを選択する実行時間は10000倍になります.
アルゴリズムの解題に使用するソートを選択するのは遅いです.
また、現在のデータの状態にかかわらず、すべての要素を無条件に比較し、位置を変更するため、効率が低下します.
References
羅東彬アルゴリズム課