見出し画像

アルゴリズム?プログラミング。 - 選択ソート

選択ソート(selection sort)は

未整列の要素の中から最大あるいは最小のものを選択し、整列済みの列の末尾に追加していくもの

https://e-words.jp/w/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88.html

リストは最初は未整列で、順番に整列していきます。今回は左端から小さい数字から順番に並ぶようにしていき、左端から整列済としていくようにコードを書いていきます。

まずリスト

num = [8,4,1,5,3]

があるとすれば、まず整列済としたい数字は"8"ということになります。

最初はこの"8"を基準に考えていきます。

この"8"ですが、このリストの中で一番小さいかな?ということで、調べていきます。

4, 1, 5, 3

8と4、8と1、8と5、8と3、と比べていきます。このときに最小値を変数minとして定義して順次比べていき、変数minに最小の数字がはいるようにします。

これをコードにすると

num = [8,4,1,5,3]

min = num[0]

for j in range(i + 1,len(num)):
     if num[min] > num[j]:
         min = j

となり、この時"min"最小値が"8"になり、"j"がリストの各数字となります。

実行すると最小値は"1"となります。

最小値が"1"となったので、今比べた"8"と"1"を入れ替えます。そして今入れ替えた場所を整列済とします。リストはというと

[1,4,8,5,3]

となり、左端の"1"は整列済みとします。

次、右隣の未整列の数字を対象にして同じ処理をくりかえます。

この操作を左端から順番の全ての数字に対して行っていき、順番に小さい数字に入れ替えていくと並び替えが完成します。

この操作をリストの数だけ繰り返せばリストの並び替えができるのでその、リスト分の繰り返しのコードを作ります。

for i in range(len(num)):

となります。そうすると全てのコードとしては

num = [8,4,1,5,3]


for i in range(len(num)):
    min = i
    for j in range(i + 1,len(num)):
        if num[min] > num[j]:
            min = j

    num[min],num[i] = num[i],num[min]

print(num)

となります。


いいなと思ったら応援しよう!