選択ソートはリストの中から一番小さい数字を見つけて、端に置き換えていくソートです。

今回は昇順とします。

配列すべてを探索し、一番小さい数字を見つけたら、左から順に収めていきます。

例：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]

結論：

ちょっと難しかった(';')