『Pythonで体験してわかるアルゴリズムとデータ構造』メモその2/選択ソートで値の交換をイメージする

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

※第2章はループの話だったので割愛。

第3章 アルゴリズムを比べる方法

書籍中では選択ソートをベースに説明されている。

この章のゴールは 入力の内容によって計算回数の大小が変化する場合の数値の比較について説明できるようになる

選択ソートについて

ja.wikipedia.org

配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。

「比較回数」は、n(n-1)/2回。「交換回数」は、各ループで最大1回なので、全体では多くともn-1回。バブルソートと比較すると、「比較回数」は同じだが「交換回数」が少ないので、選択ソートの方が高速である。

選択ソートのイメージは以下。

比較回数がなぜn(n-1)/2回なのか

何回比較したのかをn(n-1)/2で算出するのだが、なぜそうしているのか。

1からNまでの和を算出するときと同様に解いていく。
今回は配列数10なので、10マス×10マスを用意する。

選択ソートのイメージと同じように色付けしていく。
(黄色：処理対象値・橙色：処理対象と比較するデータ・青色：確定値)

そのうえでこの図を見たときに、橙色と青色が同じマス数であることが分かる（当たり前だけど）
なので、単純に「縦×横÷2」の三角形を求める公式で出せば、回答が導き出せる。

わけじゃない。
その場合 10×10÷2=50 となるのだが、マスを数えてみると45なので、結果が違う。

その5の差が黄色の考慮になる。
値が合わないのは、50の中には処理対象のデータが存在するため。
そいつらは交換元のデータなので、省いてやる必要がある。

上の図で見た通り、1行に黄色ハイライトされているマスはひとつ。
今回10マスなので、実際に考えなければいけないのは9マス。

そのため、n(n-1)/2で算出する。

交換回数がなぜn-1回なのか

上の図の通り、10処理目は交換する対象が存在しないので、交換をする必要なく確定するので、nではなく、n-1となる。

実装

def selection_sort(array):
    n = len(array)

    for i in range(0, n-1):
        print("{}回目処理".format(str(i+1)))
        min = i
        print("処理対象：", array[min])
        print("比較対象：", array[min+1:])
        
        for j in range(i+1, n):
            if array[min] > array[j]:
                min = j
        
        tmp = array[min]
        print("移動する値：", tmp)
        # 処理対象値を入れ替える配列要素に移動
        array[min], array[i] = array[i], tmp
        print("{}を{}番目に移動：{}".format(array[i], min+1, array))
        print("{}を{}番目に移動し確定：{}".format(tmp, i, array))
        print("")

array = [1,2,3,4,5,3,2,1,3,0]
print("処理前：", array)
print("")
selection_sort(array)
print("処理後 ", array)

処理前： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

1回目処理
処理対象： 1
比較対象： [2, 3, 4, 5, 3, 2, 1, 3, 0]
移動する値： 0
0を10番目に移動：[0, 2, 3, 4, 5, 3, 2, 1, 3, 1]
0を0番目に移動し確定：[0, 2, 3, 4, 5, 3, 2, 1, 3, 1]

2回目処理
処理対象： 2
比較対象： [3, 4, 5, 3, 2, 1, 3, 1]
移動する値： 1
1を8番目に移動：[0, 1, 3, 4, 5, 3, 2, 2, 3, 1]
1を1番目に移動し確定：[0, 1, 3, 4, 5, 3, 2, 2, 3, 1]

3回目処理
処理対象： 3
比較対象： [4, 5, 3, 2, 2, 3, 1]
移動する値： 1
1を10番目に移動：[0, 1, 1, 4, 5, 3, 2, 2, 3, 3]
1を2番目に移動し確定：[0, 1, 1, 4, 5, 3, 2, 2, 3, 3]

4回目処理
処理対象： 4
比較対象： [5, 3, 2, 2, 3, 3]
移動する値： 2
2を7番目に移動：[0, 1, 1, 2, 5, 3, 4, 2, 3, 3]
2を3番目に移動し確定：[0, 1, 1, 2, 5, 3, 4, 2, 3, 3]

5回目処理
処理対象： 5
比較対象： [3, 4, 2, 3, 3]
移動する値： 2
2を8番目に移動：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3]
2を4番目に移動し確定：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3]

6回目処理
処理対象： 3
比較対象： [4, 5, 3, 3]
移動する値： 3
3を6番目に移動：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3]
3を5番目に移動し確定：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3]

7回目処理
処理対象： 4
比較対象： [5, 3, 3]
移動する値： 3
3を9番目に移動：[0, 1, 1, 2, 2, 3, 3, 5, 4, 3]
3を6番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 5, 4, 3]

8回目処理
処理対象： 5
比較対象： [4, 3]
移動する値： 3
3を10番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5]
3を7番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5]

9回目処理
処理対象： 4
比較対象： [5]
移動する値： 4
4を9番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5]
4を8番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5]

処理後  [0, 1, 1, 2, 2, 3, 3, 3, 4, 5]

参考

[Python] 選択ソートの実装方法とアルゴリズム │ Web備忘録