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

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

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

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

アルゴリズム

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

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番目をスワップする場合は以下の通り。

実装例

以上のことに気をつけて実装すると以下のようになります。

 

終わり。