【Python】選択ソートを実装してみた

今日はPythonで選択ソートを実装してみました。

選択ソートはバブルソートと同じくらいにシンプルなアルゴリズムで、実装しやすいのが特徴です。

まずはアルゴリズムから解説していきたいと思います。

アルゴリズム

以下の例をみていきます。

 [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. 左から1番目の数値(target:15)を取り出し、それ以外のリストから最小値(minimam:11)を選びます。
  2. targetの方が値が大きければその2つの値をスワップします。
  3. 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

 

終わり。