選択ソートはリストの中から一番小さい数字を見つけて、端に置き換えていくソートです。
今回は昇順とします。
配列すべてを探索し、一番小さい数字を見つけたら、左から順に収めていきます。
例：3,2,1という配列があったら。
1:3,2,1
2:1,3,2
3:1,2,3
となります。
前回の、バブルソートより早くソートできました。
バブルソートと同じく、配列の要素数をi,jでループしてソートします。
まず素直にそのまま書いてみる：
sortary = [9, 7, 6, 8, 5, 3]
def selection_sort(array):
cnt = 0
n = len(array)
for i in range(0, n):
min = i#minは小さい数字の入っている、配列の要素番号
#比較のために、仮に一番数字が一番左（i番目）とする
for j in range(i+1, n):
#min=iとしているため、iが一番小さい数字と仮定してi+1からループが始まる。
cnt = cnt + 1
print(cnt, i, j, array)
if array[min] > array[j]:
#minが更新判定
min = j#minを更新
#minとtmpを使って、配列の入れ替え
tmp = array[i]
array[i] = array[min]
array[min] = tmp
return array
print(selection_sort(sortary))
バブルソートのjのループで、(0,n-i-1)というfor分がありましたが、選択ソートでは、jのループで,
i+1としているため、すでに確定された最小値はソートから除外されます。
結果：
1 0 1 [9, 7, 6, 8, 5, 3]
2 0 2 [7, 9, 6, 8, 5, 3]
3 0 3 [6, 9, 7, 8, 5, 3]
4 0 4 [6, 9, 7, 8, 5, 3]
5 0 5 [5, 9, 7, 8, 6, 3]
6 1 2 [3, 9, 7, 8, 6, 5]
7 1 3 [3, 7, 9, 8, 6, 5]
8 1 4 [3, 8, 9, 7, 6, 5]
9 1 5 [3, 6, 9, 7, 8, 5]
10 2 3 [3, 5, 9, 7, 8, 6]
11 2 4 [3, 5, 7, 9, 8, 6]
12 2 5 [3, 5, 8, 9, 7, 6]
13 3 4 [3, 5, 6, 9, 7, 8]
14 3 5 [3, 5, 6, 7, 9, 8]
15 4 5 [3, 5, 6, 8, 9, 7]
[3, 5, 6, 8, 7, 9]
もっと初心者チックに記述すると(マネするな）
sortary = [9, 7, 6, 8, 5, 3]
def selection_sort(array):
cnt = 0
n = len(array)
for i in range(0, n):#←ここら辺が初心者
min = i#minは小さい数字の入っている、配列の要素番号
#比較のために、仮に一番数字が一番左（i番目）とする
for j in range(0, n):#←ここら辺が初心者
#min=iとしているため、iが一番小さい数字と仮定してi+1からループが始まる。
cnt = cnt + 1
print(cnt, i, j, array)
if array[min] < array[j]:#??????
#minが更新判定
min = j#minを更新
#mintotmpを使って、配列の入れ替え
tmp = array[i]
array[i] = array[min]
array[min] = tmp
return array
print(selection_sort(sortary))
if array[min] < array[j]:にしないと、反転します。
あれ、バブルソート？もどきの変な結果になりました。（笑）
このコードは忘れましょう。
1 0 0 [9, 7, 6, 8, 5, 3]
2 0 1 [9, 7, 6, 8, 5, 3]
3 0 2 [9, 7, 6, 8, 5, 3]
4 0 3 [9, 7, 6, 8, 5, 3]
5 0 4 [9, 7, 6, 8, 5, 3]
6 0 5 [9, 7, 6, 8, 5, 3]
7 1 0 [9, 7, 6, 8, 5, 3]
8 1 1 [7, 9, 6, 8, 5, 3]
9 1 2 [7, 9, 6, 8, 5, 3]
10 1 3 [7, 9, 6, 8, 5, 3]
11 1 4 [7, 9, 6, 8, 5, 3]
12 1 5 [7, 9, 6, 8, 5, 3]
13 2 0 [7, 9, 6, 8, 5, 3]
14 2 1 [6, 9, 7, 8, 5, 3]
15 2 2 [6, 7, 9, 8, 5, 3]
16 2 3 [6, 7, 9, 8, 5, 3]
17 2 4 [6, 7, 9, 8, 5, 3]
18 2 5 [6, 7, 9, 8, 5, 3]
19 3 0 [6, 7, 9, 8, 5, 3]
20 3 1 [6, 7, 9, 8, 5, 3]
21 3 2 [6, 7, 9, 8, 5, 3]
22 3 3 [6, 7, 8, 9, 5, 3]
23 3 4 [6, 7, 8, 9, 5, 3]
24 3 5 [6, 7, 8, 9, 5, 3]
25 4 0 [6, 7, 8, 9, 5, 3]
26 4 1 [5, 7, 8, 9, 6, 3]
27 4 2 [5, 6, 8, 9, 7, 3]
28 4 3 [5, 6, 7, 9, 8, 3]
29 4 4 [5, 6, 7, 8, 9, 3]
30 4 5 [5, 6, 7, 8, 9, 3]
31 5 0 [5, 6, 7, 8, 9, 3]
32 5 1 [3, 6, 7, 8, 9, 5]
33 5 2 [3, 5, 7, 8, 9, 6]
34 5 3 [3, 5, 6, 8, 9, 7]
35 5 4 [3, 5, 6, 7, 9, 8]
36 5 5 [3, 5, 6, 7, 8, 9]
[3, 5, 6, 7, 8, 9]
chatGPTに添削依頼を出す
sortary = [9, 7, 6, 8, 5, 3]
def selection_sort(array):
cnt = 0
n = len(array)
for i in range(0, n):#(0,n-1)のほうがさらに効率よし。
min = i # 最小の要素のインデックスを保持する変数
for j in range(i+1, n):
cnt = cnt + 1
print(cnt, i, j, array)
if array[min] > array[j]:
min = j # 最小の要素のインデックスを更新
# ループが終了した後に交換
if i != min:
tmp = array[i]
array[i] = array[min]
array[min] = tmp
return array
print(selection_sort(sortary))
自分の書いたコードでは、jのループで交換をしていましたが、jのループを抜けた後交換するほうが効率が良いようです。
jのループ内で交換をすると、即時交換となり交換回数が増えます。
jのループが終わり、最小値が決まった後で交換するほうが効率がいいですよね～
いわれてみればそうかもしれない。
結果は変わらずですが、データ量が増えると結構かわるとのお達し。
1 0 1 [9, 7, 6, 8, 5, 3]
2 0 2 [9, 7, 6, 8, 5, 3]
3 0 3 [9, 7, 6, 8, 5, 3]
4 0 4 [9, 7, 6, 8, 5, 3]
5 0 5 [9, 7, 6, 8, 5, 3]
6 1 2 [3, 7, 6, 8, 5, 9]
7 1 3 [3, 7, 6, 8, 5, 9]
8 1 4 [3, 7, 6, 8, 5, 9]
9 1 5 [3, 7, 6, 8, 5, 9]
10 2 3 [3, 5, 6, 8, 7, 9]
11 2 4 [3, 5, 6, 8, 7, 9]
12 2 5 [3, 5, 6, 8, 7, 9]
13 3 4 [3, 5, 6, 8, 7, 9]
14 3 5 [3, 5, 6, 8, 7, 9]
15 4 5 [3, 5, 6, 7, 8, 9]
[3, 5, 6, 7, 8, 9]
結論：
ちょっと難しかった(';')