選択ソートとはデータの集合をある決まりに従って並び替えるソートアルゴリズムの一種です。
今回は
array = [5,4,6,9,2,7,8,1,3] → array = [1,2,3,4,5,6,7,8,9]
arrayの中身をリストを数字の小さい順に並び替える選択ソートを考えます。
ちなみにもしリスト型のメソッドを使うなら array.sort() で小さい順に並び変わります。
選択ソート (Selectionsort)
アルゴリズム
今回自分が書いた選択ソートは左から順番(小さいインデックスから順に)に小さい数のデータと交換していきます。
例えば、
[5, 4, 6, 9, 2, 7, 8, 1, 3]
という状態なら
１番最初の５とそれより右の要素の中で一番数の少ない１（インデックス７）と交換します。
[1, 2, 6, 9, 4, 7, 8, 5, 3]
という状態なら１、２はすでに小さい順にソートされているので、３番目（インデックス２）の６とそれより右の要素の中で一番数の少ない３（インデックス８）と交換します。
見て分かる通り、選択ソートは端（僕のコードの場合は左）から順番にルールを満たすように完璧に並び替えていきます。
実際のコード
コードの解説
全体の流れ
selectionsortという関数が選択ソートの機能を持っている部分になります。
内部にたくさんのprint()がありますが、これらはどのようにソートしているかを確認するためだけに入れているので本来は必要ありません。
メインコードではarrayを用意して、それをパラメーターとしてselectionsort関数を呼び出して、その関数が返したソートされたarrayを出力するコードになっています。
一番目の forループ
最初の forループは一番小さい値と交換する場所を順番に動かしています。
実行結果の1 time, 2 timeと数字が動いているのはこのループの i の値が変わっていることを意味します。
先ほど「選択ソートは端（僕のコードの場合は左）から順番にルールを満たすように完璧に並び替えていきます。」と言いましたが、このループが端から（左から）並び替える部分を動かしています。
細かい技術的な話もすると
rangeの後にlen(arraay)-1とarrayのサイズから１引いているのは、このforループはリストのインデックスを0から最後まで回す役割があるので、最後の要素はリストの大きさー１がインデックスの値になります。
2番目のfor ループ
２番目のforループでは１つ目のループの変数のiより右側にある一番低い値を探します。
ちなみに forループのrange(i+1, len(somelist))はi+1からlen(somelist)の一つ前までのループになります。
例えば
for i in range(2,4):
print(i)
2
3
iよりも右側のインデックスを回し、もし小さい値が合った時はif文の処理が実行され、そのインデックスをmini_indexに覚えさせてあとで交換に使います。
もしインデックス i の値が最小の場合if文は実行されず、すでにmin_indexには i が代入されているため、iとi 番目が交換、すなわち何も行われず、iが次の数になります。
実行結果
1 time
[5, 4, 6, 9, 2, 7, 8, 1, 3]
i 5 min_index 1
[1, 4, 6, 9, 2, 7, 8, 5, 3]
2 time
[1, 4, 6, 9, 2, 7, 8, 5, 3]
i 4 min_index 2
[1, 2, 6, 9, 4, 7, 8, 5, 3]
3 time
[1, 2, 6, 9, 4, 7, 8, 5, 3]
i 6 min_index 3
[1, 2, 3, 9, 4, 7, 8, 5, 6]
4 time
[1, 2, 3, 9, 4, 7, 8, 5, 6]
i 9 min_index 4
[1, 2, 3, 4, 9, 7, 8, 5, 6]
5 time
[1, 2, 3, 4, 9, 7, 8, 5, 6]
i 9 min_index 5
[1, 2, 3, 4, 5, 7, 8, 9, 6]
6 time
[1, 2, 3, 4, 5, 7, 8, 9, 6]
i 7 min_index 6
[1, 2, 3, 4, 5, 6, 8, 9, 7]
7 time
[1, 2, 3, 4, 5, 6, 8, 9, 7]
i 8 min_index 7
[1, 2, 3, 4, 5, 6, 7, 9, 8]
8 time
[1, 2, 3, 4, 5, 6, 7, 9, 8]
i 9 min_index 8
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
以上が実行結果です。選択ソートがどのように並び替えているかチェックして見てください。
他にも色々なアルゴリズムの講座を開設していきたいと思います。もしご興味のある方はまた覗いて見てください。
すでに上がっているアルゴリズムの記事はこれらになります。
別のソートアルゴリズムを見てみたい方はこちら
