すのふら

すのふら

日々の備忘録

『Pythonで体験してわかるアルゴリズムとデータ構造』メモその5/バブルソートを改良しよう

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

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

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



第5章 アルゴリズムを改良するコツ

この章のゴールは アルゴリズムを改良するには、どこに着目すればよいか

書籍中ではバブルソートを例にとって説明している。



バブルソートについて

バブルソート

ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。(単に交換法と言う場合もある)
バブルソート - Wikipedia

この動画を見るとどういう処理か分かりやすい。

www.youtube.com

要は背比べを順番にやっていくだけのソート。

全要素について確認を行っていくため最良計算時間はO(n)、平均計算時間はO(n2)。

平均計算時間がO(n2)なので、以下にもある通り、値の比較をn-1回を続けるため。

イメージは以下となる。

f:id:snofra:20190923005506p:plain



実装

def bubble_sort(array):
    n = len(array)
    for i in range(0, n-1):
        print("{}回目処理".format(str(i+1)))
        for j in range(0, n-1):
            print("処理対象{}・比較対象{}".format(array[j],array[j+1]))

            if array[j+1] < array[j]:
                array[j+1], array[j] = array[j], array[j+1]
            print(array)
        print("{}回目処理終了".format(str(i+1)))
        print()

array = [1,2,3,4,5,3,2,1,7,0]
print("処理前:", array)
print("")
bubble_sort(array)
print("処理後 ", array)
処理前: [1, 2, 3, 4, 5, 3, 2, 1, 7, 0]

1回目処理
処理対象1・比較対象2
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象2・比較対象3
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象3・比較対象4
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象4・比較対象5
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象5・比較対象3
[1, 2, 3, 4, 3, 5, 2, 1, 7, 0]
処理対象5・比較対象2
[1, 2, 3, 4, 3, 2, 5, 1, 7, 0]
処理対象5・比較対象1
[1, 2, 3, 4, 3, 2, 1, 5, 7, 0]
処理対象5・比較対象7
[1, 2, 3, 4, 3, 2, 1, 5, 7, 0]
処理対象7・比較対象0
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
1回目処理終了

2回目処理
処理対象1・比較対象2
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象2・比較対象3
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象3・比較対象4
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象4・比較対象3
[1, 2, 3, 3, 4, 2, 1, 5, 0, 7]
処理対象4・比較対象2
[1, 2, 3, 3, 2, 4, 1, 5, 0, 7]
処理対象4・比較対象1
[1, 2, 3, 3, 2, 1, 4, 5, 0, 7]
処理対象4・比較対象5
[1, 2, 3, 3, 2, 1, 4, 5, 0, 7]
処理対象5・比較対象0
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象5・比較対象7
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
2回目処理終了

3回目処理
処理対象1・比較対象2
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象2・比較対象3
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象3・比較対象3
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象3・比較対象2
[1, 2, 3, 2, 3, 1, 4, 0, 5, 7]
処理対象3・比較対象1
[1, 2, 3, 2, 1, 3, 4, 0, 5, 7]
処理対象3・比較対象4
[1, 2, 3, 2, 1, 3, 4, 0, 5, 7]
処理対象4・比較対象0
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象4・比較対象5
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象5・比較対象7
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
3回目処理終了

4回目処理
処理対象1・比較対象2
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象2・比較対象3
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象3・比較対象2
[1, 2, 2, 3, 1, 3, 0, 4, 5, 7]
処理対象3・比較対象1
[1, 2, 2, 1, 3, 3, 0, 4, 5, 7]
処理対象3・比較対象3
[1, 2, 2, 1, 3, 3, 0, 4, 5, 7]
処理対象3・比較対象0
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象4・比較対象5
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象5・比較対象7
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
4回目処理終了

5回目処理
処理対象1・比較対象2
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象1
[1, 2, 1, 2, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 2, 1, 2, 3, 0, 3, 4, 5, 7]
処理対象3・比較対象0
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象4・比較対象5
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象5・比較対象7
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
5回目処理終了

6回目処理
処理対象1・比較対象2
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象1
[1, 1, 2, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 1, 2, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象0
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象4・比較対象5
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象5・比較対象7
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
6回目処理終了

7回目処理
処理対象1・比較対象1
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象2
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象0
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象4・比較対象5
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象5・比較対象7
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
7回目処理終了

8回目処理
処理対象1・比較対象1
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象0
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象2
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象4・比較対象5
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象5・比較対象7
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
8回目処理終了

9回目処理
処理対象1・比較対象0
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象1
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象2
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象3
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象3・比較対象4
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象4・比較対象5
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象5・比較対象7
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
9回目処理終了

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

アルゴリズムを改良する

実装したバブルソートは、すでに確定してしまっている桁数に対してももう一度交換してしまっている。

これは無駄な処理なので、確定済については処理しないように実装する。

def bubble_sort(array):
    n = len(array)
    end_exchenge=n
    for i in range(0, n-1):
        print("{}回目処理".format(str(i+1)))
        
        for j in range(0, n-1):
            # すでに確定してしまった処理はスキップする
            if end_exchenge == j:
                break;

            print("処理対象{}・比較対象{}".format(array[j],array[j+1]))
            if array[j+1] < array[j]:
                array[j+1], array[j] = array[j], array[j+1]
            print(array)
            
        end_exchenge -= 1
        print("{}回目処理終了".format(str(i+1)))
        print()

array = [1,2,3,4,5,3,2,1,7,0]
print("処理前:", array)
print("")
bubble_sort(array)
print("処理後 ", array)
処理前: [1, 2, 3, 4, 5, 3, 2, 1, 7, 0]

1回目処理
処理対象1・比較対象2
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象2・比較対象3
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象3・比較対象4
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象4・比較対象5
[1, 2, 3, 4, 5, 3, 2, 1, 7, 0]
処理対象5・比較対象3
[1, 2, 3, 4, 3, 5, 2, 1, 7, 0]
処理対象5・比較対象2
[1, 2, 3, 4, 3, 2, 5, 1, 7, 0]
処理対象5・比較対象1
[1, 2, 3, 4, 3, 2, 1, 5, 7, 0]
処理対象5・比較対象7
[1, 2, 3, 4, 3, 2, 1, 5, 7, 0]
処理対象7・比較対象0
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
1回目処理終了

2回目処理
処理対象1・比較対象2
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象2・比較対象3
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象3・比較対象4
[1, 2, 3, 4, 3, 2, 1, 5, 0, 7]
処理対象4・比較対象3
[1, 2, 3, 3, 4, 2, 1, 5, 0, 7]
処理対象4・比較対象2
[1, 2, 3, 3, 2, 4, 1, 5, 0, 7]
処理対象4・比較対象1
[1, 2, 3, 3, 2, 1, 4, 5, 0, 7]
処理対象4・比較対象5
[1, 2, 3, 3, 2, 1, 4, 5, 0, 7]
処理対象5・比較対象0
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象5・比較対象7
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
2回目処理終了

3回目処理
処理対象1・比較対象2
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象2・比較対象3
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象3・比較対象3
[1, 2, 3, 3, 2, 1, 4, 0, 5, 7]
処理対象3・比較対象2
[1, 2, 3, 2, 3, 1, 4, 0, 5, 7]
処理対象3・比較対象1
[1, 2, 3, 2, 1, 3, 4, 0, 5, 7]
処理対象3・比較対象4
[1, 2, 3, 2, 1, 3, 4, 0, 5, 7]
処理対象4・比較対象0
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象4・比較対象5
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
3回目処理終了

4回目処理
処理対象1・比較対象2
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象2・比較対象3
[1, 2, 3, 2, 1, 3, 0, 4, 5, 7]
処理対象3・比較対象2
[1, 2, 2, 3, 1, 3, 0, 4, 5, 7]
処理対象3・比較対象1
[1, 2, 2, 1, 3, 3, 0, 4, 5, 7]
処理対象3・比較対象3
[1, 2, 2, 1, 3, 3, 0, 4, 5, 7]
処理対象3・比較対象0
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象3・比較対象4
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
4回目処理終了

5回目処理
処理対象1・比較対象2
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 2, 2, 1, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象1
[1, 2, 1, 2, 3, 0, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 2, 1, 2, 3, 0, 3, 4, 5, 7]
処理対象3・比較対象0
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象3・比較対象3
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
5回目処理終了

6回目処理
処理対象1・比較対象2
[1, 2, 1, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象1
[1, 1, 2, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 1, 2, 2, 0, 3, 3, 4, 5, 7]
処理対象2・比較対象0
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象3
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
6回目処理終了

7回目処理
処理対象1・比較対象1
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象2
[1, 1, 2, 0, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象0
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象2・比較対象2
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
7回目処理終了

8回目処理
処理対象1・比較対象1
[1, 1, 0, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象0
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象2
[1, 0, 1, 2, 2, 3, 3, 4, 5, 7]
8回目処理終了

9回目処理
処理対象1・比較対象0
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
処理対象1・比較対象1
[0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
9回目処理終了

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