今日はPythonで選択ソートを実装してみました。
選択ソートはバブルソートと同じくらいにシンプルなアルゴリズムで、実装しやすいのが特徴です。
まずはアルゴリズムから解説していきたいと思います。
[toc]アルゴリズム
以下の例をみていきます。
[15, 34, 28, 11, 36, 21, 42] target: 15 minimam: 11 [11, 34, 28, 15, 36, 21, 42] target: 34 minimam: 15 [11, 15, 28, 34, 36, 21, 42] :
1番上のリストが与えられた未整列の物です。
- 左から1番目の数値(target:15)を取り出し、それ以外のリストから最小値(minimam:11)を選びます。
- targetの方が値が大きければその2つの値をスワップします。
- 1と2の処理を、左から2番目、左から3番目、、の値にも繰り返し適用し、リストの最後まで行ったら終了です。
コード
リストの中の最小値とインデックスを取得する方法
このコードを実装するにあたり難しいのが、最小値を選ぶ処理です。
最小値を選ぶだけでなくスワップすることを考えて、リストの何番目にあるかを示すインデックスが必要になります。
リストの中の最小値は、min()
を使えば取得することができます。
インデックスは、`index()`を使います。
これを組み合わせて、`A_list.index(min(A_list))`とすることで、リスト中の最小値があるインデックスを取得することができます。
リストの値をスワップする方法
Pythonだと値のスワップは1行で実装できます。
例えば、0番目と1番目をスワップする場合は以下の通り。
A_list[0],A_list[1] = A_list[1],A_list[0]
実装例
以上のことに気をつけて実装すると以下のようになります。
def Selection_Sort(num_list): for i in range(len(num_list)-1): min_value = min(num_list[i+1:]) min_idx = num_list.index(min(num_list[i+1:])) if num_list[i] > min_value: num_list[i],num_list[min_idx] = num_list[min_idx],num_list[i] return num_list
終わり。