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

今日は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. 左から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

 

終わり。

2 件のコメント

  • 実装例のsample_listはnum_listですか?
    同じ値がリスト内にある場合にソートし終えた値のインデックスを取ってきてしまい、ソートが失敗してしまいます。

    • コメントありがとうございます。
      ご指摘の通り、num_listでしたので修正しました。

      同じ値がリスト内にある場合の対応については考えていませんでした。
      時間のある時に検討してみます。

  • コメントを残す

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    ABOUTこの記事をかいた人

    個人アプリ開発者。Python、Swift、Unityのことを発信します。月間2.5万PVブログ運営。 Twitter:@yamagablog