質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

3回答

5920閲覧

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

kousei0109

総合スコア7

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

4クリップ

投稿2020/06/29 02:31

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になります。
これをどうにかして比較回数を最小の30まで減らしたいのですが詳しい方がいたら教えてください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

momon-ga

2020/06/29 02:41

要素10個のバブルソートの比較回数の最小は45でいいのでは?
dodox86

2020/06/29 02:48

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

2020/06/30 01:00

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

回答3

0

ベストアンサー

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

Diff

1-for i in range(n-1): 2+i = 0 3+while i < n-1: 4 for j in range(n-1,i,-1): 5 ccnt += 1 6 if list[j-1] > list[j]: 7 list[j-1],list[j] = list[j],list[j-1] 8+ i = j - 1 9 ecnt += 1 10 11+ i += 1

追記

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

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

コードの貼り方について

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

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

投稿2020/06/29 04:31

編集2020/06/29 11:30
LouiS0616

総合スコア35668

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

anndonut

2020/06/29 07:21 編集

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

2020/06/29 07:20

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

2020/06/29 07:55

> 一般的にバブルソートはN(N-1)/2回比較を行うもの ナイーブな実装だとその比較回数だと思いますが、比較回数自体が定義に影響するのですか?
LouiS0616

2020/06/29 08:15 編集

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

2020/06/29 08:30

バブルソートと呼べると思います。あとはプログラムの正当性の証明なのですが、LouiS0616さんがどうしてこのアルゴリズムを書いたのか、ということが問題になると思います。そもそもソートについての問題を多く解いていてバブルソートについてはこの改良が可能であることを「直感的に理解している」のか、文献を参考にしているのか、知り合いから教わったのか、そもそも日本語と図による説明も可能ではあるが単に省略したということか、ということですね。 とりあえずC++のnext_permutationを使ってn=4, 8, 10の場合で[1, ..., N]の順列の全組み合わせを試験しましたが誤りは見つかりませんでした。ソートは、リスト内に同じ要素を含む場合に動作がおかしくなることもあるのでその場合についても試験する必要がありますが、恐らく正しく動作するのでしょう。反証をするのはあきあらめました。
LouiS0616

2020/06/29 08:49

プログラミングに入門したての頃、サンプルコードとしてこのようなコードに触れました。 一般的にどう呼称される効率化なのかは分かりません。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

2020/06/29 08:50

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

2020/06/29 08:57

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

2020/06/29 11:01

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

2020/06/29 11:35 編集

@hope_mucci さん コメントありがとうございます。 リンク先拝見しました。まさにこれですね。 > 質問者さんへの問題解決にはコードだけでなくこのような解説が必要かと存じます。 そうですね、その方が丁寧だと思います。回答で紹介させて頂きます。
dodox86

2020/06/29 18:01

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

2020/06/30 08:21

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

2020/07/04 04:27 編集

@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 ⇒ 配列がある性質を満たす ことは示していますが、その逆が成立することには文中で触れていないですよね。 重箱の隅かもですが、自明とまでは言えない気がします。 --- ケチを付けるような形になって恐縮ですが、お許し願います。このように議論する機会はあまり無いですから。 単に私の理解が追い付いていない可能性も充分あり得ます。その場合はごめんなさい。
kousei0109

2020/07/06 02:09

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

0

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

バブルソートの改良

Python3

1def bubble_sort(list): 2 n = len(list) 3 ccnt = 0 # 比較回数 4 ecnt = 0 # 交換回数 5 6 for i in range(n-1): 7 sorted = True # ステップ終了時にソートが完了しているか確認するフラグ 8 for j in range(n-1,i,-1): 9 ccnt += 1 10 if list[j-1] > list[j]: 11 list[j-1],list[j] = list[j],list[j-1] 12 sorted = False 13 ecnt += 1 14 if sorted: break 15 16 print(f'比較回数 ⇒ {ccnt}') 17 print(f'交換回数 ⇒ {ecnt}') 18 19 return list 20 21list = [3,1,4,2,5,6,10,8,7,9] 22print(f'----- バブルソート -----') 23print("並び替え前 ⇒ " + str(list)) 24sorted_list = bubble_sort(list) 25print("並び替え後 ⇒ " + str(sorted_list))

投稿2020/06/29 08:54

anndonut

総合スコア667

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kousei0109

2020/06/30 08:22

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

0

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

投稿2020/06/29 22:49

編集2020/06/29 22:51
AMK

総合スコア765

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kousei0109

2020/06/30 08:22

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問