選択ソートとは
- リストから最も小さい要素を選んで前に移動する方法
- 最小の要素とリストの先頭の値を交換する
- 最小の要素は先頭から線形探索で調べる
コード
|
1 2 3 4 5 6 7 8 9 10 11 |
data = [3,2,5,6,1,8,2,10,4,7,9] for i in range(len(data)): ＃dataの要素数だけループ min = i ＃１ for j in range(i+1,len(data)): ＃iの次の要素からdataの最後までループ if data[min] > data[j]: ＃２現在の最小値よりも小さい値が見つかった場合 min = j ＃最小値のインデックスを更新 data[i],data[min] = data[min], data[i] ＃３ print(data) ＃[1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
＃１ minに最小値の位置をセット
”for i in range(len(data)):” この１つめのループでリストであるdataの要素数だけループします。
ループ変数ｉは０から始まります。最終的には昇順で小さい値を前から置いていくことになるので、ｉの値がそのまま最小値の位置になります。
＃２ 最小値を調べる
２つめのループの中では、data内の最小値を調べています。
data[j]が現在の最小値であるdata[min]よりも小さい場合は、”min = j”として最小値を示すインデックスを交換します。これでdata[min]が最小値へ更新されます。
dataの最後までこれを繰り返すのでdata[min]はまた更新される可能性があります。
＃３最小値の位置を交換
”data[i],data[min] = data[min], data[i]”
data[i]はi番目のリストの要素であり、data[min]は２つめのループにより見つかった最小値です。
この２つの位置をdata内で入れ替えることにより、i番目の最小値を更新します。
参考書籍
こちらの書籍を参考にしています。
初めてアルゴリズムを勉強する人を対象に書かれた本だと思います。
知らない分野について勉強するときはわからないことや理解できないことが連続するので、集中して勉強を続けることができず辛いことが多いですが、そんな私のような初学者でも続けられるように、重たくならない内容で説明されています。
コメント