Python バブルソートについて 比較回数を減らしたい

Question

def bubble_sort(list):
n = len(list)
ccnt = 0 # 比較回数
ecnt = 0 # 交換回数

for i in range(n-1):
    for j in range(n-1,i,-1):
        ccnt += 1
        if list[j-1] > list[j]:
            list[j-1],list[j] = list[j],list[j-1]
            ecnt += 1
            
print(f'比較回数 ⇒ {ccnt}')
print(f'交換回数 ⇒ {ecnt}')

return list

list = [3,1,4,2,5,6,10,8,7,9]
print(f'----- バブルソート -----')
print("並び替え前 ⇒ " + str(list))
sorted_list = bubble_sort(list)
print("並び替え後 ⇒ " + str(sorted_list))

これは、listの中の数字を比較し、交換して小さい順に並べるプログラミングなのですが上記のコードだと比較回数が45になります。
これをどうにかして比較回数を最小の３０まで減らしたいのですが詳しい方がいたら教えてください。

Comments

[momon-ga]

要素１０個のバブルソートの比較回数の最小は４５でいいのでは？

[dodox86]

「バブルソートとはそういうものだ」ということを理解されていないのだと思います。
常に、(n-1)+(n-2)+(n-3)...(n-(n-1))回比較するのがバブルソートの仕様です。違うソート方法を実装せよ、と言う課題なのではないでしょうか。

[miyabi_pudding]

バブルソートより、クイックソートの方が早いし、比較回数が少ないと、見たことがあるのですが、
あくまでバブルソートでなくてはいけないのでしょうか？
ソート法自体の検討と改善なのであれば、クイックソートについて調べてみるといいかも。

Answer 1

24回まで減っちゃいました。

-for i in range(n-1):
+i = 0
+while i < n-1:
     for j in range(n-1,i,-1):
         ccnt += 1
         if list[j-1] > list[j]:
             list[j-1],list[j] = list[j],list[j-1]
+            i = j - 1
             ecnt += 1
                
+    i += 1

追記

コメント欄でhope_mucciさんが次の解説スライドを紹介して下さいました。
https://www.math.ryukoku.ac.jp/~qma/education/algo/ALGO-3-forWEB.pdf

段階を踏んだ解説が読めますので、是非ご参照下さい。

コードの貼り方について

teratailには、コードを見やすく表示する機能があります。
質問編集画面を開き、コードを選択した状態で<code>ボタンを押して下さい。

特にPythonの場合、インデントが崩れるとコードの意味が変わってしまいます。

Comments

[anndonut]

LouiS0616さん、質問への追記・修正依頼を読んでください。一般的にバブルソートはN(N-1)/2回比較を行うものなので何らかの説明が必要です。恐らく、比較を行わなくてよいアルゴリズム的な改良が入っているものと思いますけれども。ちなみにAOJのバブルソートのページを貼っておきます。
http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_2_A&pattern=post&type=general&filter=Algorithm

[LouiS0616]

読みましたが、何か問題あるでしょうか？

[LouiS0616]

> 一般的にバブルソートはN(N-1)/2回比較を行うもの

ナイーブな実装だとその比較回数だと思いますが、比較回数自体が定義に影響するのですか？

[LouiS0616]

私の方法は、次の全てを満たしています。バブルソートと呼べるのでは？
(a) ソート済みの部分配列が片側にできていく（泡が浮いていく）
(b) 隣り合った要素のみを比較し、必要に応じてスワップする
(c) 平均計算量は二乗オーダ

[anndonut]

バブルソートと呼べると思います。あとはプログラムの正当性の証明なのですが、LouiS0616さんがどうしてこのアルゴリズムを書いたのか、ということが問題になると思います。そもそもソートについての問題を多く解いていてバブルソートについてはこの改良が可能であることを「直感的に理解している」のか、文献を参考にしているのか、知り合いから教わったのか、そもそも日本語と図による説明も可能ではあるが単に省略したということか、ということですね。

とりあえずC++のnext_permutationを使ってn=4, 8, 10の場合で[1, ..., N]の順列の全組み合わせを試験しましたが誤りは見つかりませんでした。ソートは、リスト内に同じ要素を含む場合に動作がおかしくなることもあるのでその場合についても試験する必要がありますが、恐らく正しく動作するのでしょう。反証をするのはあきあらめました。

[LouiS0616]

プログラミングに入門したての頃、サンプルコードとしてこのようなコードに触れました。
一般的にどう呼称される効率化なのかは分かりません。newboundという名の変数が使われていたことだけは覚えています。（実際に bubble sort "newbound" で検索すると同様のコードがヒットします）

直感的にというか、バブルソートは泡のように最小要素が浮き上がりますよね？
値の交換が起こらなかった個所については、既に順序が揃っていると見做して問題無いのです。
1 2 3 5 6 4 9 7 8 を『ふるう』と、1 2 3 4 5 6 7 9 8 になります。最後に交換したのは4と5ですが、逆に言えばこれ以降の交換が発生しなかったのは 1 2 3 がたまたま『ソート済み』だったからです。

[LouiS0616]

境界値とかでバグを踏んでる可能性は否定できないですけれど。

[anndonut]

LouiS0616さん、コードの詳細についてご回答ありがとうございます。とても参考になりました。日本語による証明については多分できると思います。ちょっと整理します。

[hope_mucci]

直リンクして良いかどうかわからないけど
https://www.math.ryukoku.ac.jp/~qma/education/algo/ALGO-3-forWEB.pdf
の、改良①で30回、改良②で24回まで比較回数が減ります。
比較回数を減らせる理屈は、pdfを読めばまあわかるかな？
質問者さんへの問題解決にはコードだけでなくこのような解説が必要かと存じます。

[LouiS0616]

@hope_mucci さん
コメントありがとうございます。
リンク先拝見しました。まさにこれですね。

> 質問者さんへの問題解決にはコードだけでなくこのような解説が必要かと存じます。
そうですね、その方が丁寧だと思います。回答で紹介させて頂きます。

[dodox86]

ソートと言えばほぼ最初に出てくるのが「バブルソート」だと思うのですが、ここまで踏み込んで理解していませんでした。勉強になりました。（高評価させていただきました）

[kousei0109]

皆さん丁寧にありがとうございます。
とても勉強になります。

[anndonut]

証明書きました。n番煎じと思いますけれども。よろしければご覧になってくださいっ
https://github.com/haruo-wakakusa/proof-of-bubble-sort/blob/master/bubble-sort.pdf

[LouiS0616]

@anndonut さん
証明拝見しました。（安藤さんでも若草さんでも無かったのですね）
なかなかおもしろかったです。

さて、私の理解が及んでいないだけかもしれませんが、幾つか気になる点を挙げさせて頂きます。

---
1. 第3章『バブルソート』で『任意の正の整数 j, k について j ≤ k ≤ i ⇒ Sji ≤ Ski』をバブルソートの性質としていること

ステップ1の配列が {1, 2, 3, 8, 2} だったとき、ステップ2では {1, 2, 2, 3, 8} になります。
j ≤ k ≤ i を満たす j = 1, k = 2, i = 4 について、Sji ≤ Ski は成立しません。(8 ＞ 3)

---
2. 第1章『最小値を求める』で『y ∊ {A1, ... An} について xi ≤ y であるので』と記述していること

yは初出ですが、∀y ∊ {A1, ... An}, xi ≤ y という意味ですか？
これは当該アルゴリズムでxiが最小値になるという前提が無いと成立しないと思うのです。証明すべき事項を前提に持ってきて、循環してしまっているような気がします。

---
3. 第4章『バブルソートの改良アルゴリズム』で、『～であるので、ステップ i の計算完了時にステップ k = inext である』と導出していること

ステップi ⇒ 配列がある性質を満たす ことは示していますが、その逆が成立することには文中で触れていないですよね。
重箱の隅かもですが、自明とまでは言えない気がします。

---
ケチを付けるような形になって恐縮ですが、お許し願います。このように議論する機会はあまり無いですから。
単に私の理解が追い付いていない可能性も充分あり得ます。その場合はごめんなさい。

[anndonut]

長くなりそうなのでissueを作成して回答を書かせていただきました。
https://github.com/haruo-wakakusa/proof-of-bubble-sort/issues/1

[kousei0109]

とても丁寧にありがとうございます

Answer 2

AOJやその他のサイト(下記リンク)などで紹介されているバブルソートの改良方法です。この方式は直感的に分かりやすいと思います。

バブルソートの改良

def bubble_sort(list):
    n = len(list)
    ccnt = 0 # 比較回数
    ecnt = 0 # 交換回数
    
    for i in range(n-1):
        sorted = True # ステップ終了時にソートが完了しているか確認するフラグ
        for j in range(n-1,i,-1):
            ccnt += 1
            if list[j-1] > list[j]:
                list[j-1],list[j] = list[j],list[j-1]
                sorted = False
                ecnt += 1
        if sorted: break
    
    print(f'比較回数 ⇒ {ccnt}')
    print(f'交換回数 ⇒ {ecnt}')
    
    return list

list = [3,1,4,2,5,6,10,8,7,9]
print(f'----- バブルソート -----')
print("並び替え前 ⇒ " + str(list))
sorted_list = bubble_sort(list)
print("並び替え後 ⇒ " + str(sorted_list))

Comments

[kousei0109]

丁寧にありがとうございます。
とても分かりやすいです。

Answer 3

ソートアルゴリズムを視覚化したサイトが有ったので載せておきます
https://qiita.com/r-ngtm/items/f4fa55c77459f63a5228
言語は違うけど、見れば概念が理解できるはず

Comments

[kousei0109]

丁寧にありがとうございます。