隣接交換法のアルゴリズムについて

質問

隣接交換法(バブルソート)のアルゴリズムについて悩んでいます。

Q:配列「データ」には10個の要素があり、この配列「データ」を降順に並び替えるための隣接交換法アルゴリズムは？

一応、自分なりにアルゴリズムを考えたのですが、ループを抜けるチャンスが、【『要素』の数-1】回あるといわれ、それを考慮したアルゴリズムを考えよ、と言われました。

(そのチャンスというのが、どこにくるのかがわかりません。)

http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。

すみませんが、教えていただけないでしょうか？よろしくお願いします。

回答No.3

leaz024 · ベストアンサー

正しく書かれたバブルソートは、「要素数－１」回の外側ループと、隣接要素の比較・交換を行う内側ループの二重ループ構造となります。この二重ループが全て実行されればソートは完了するわけですが、元のデータの並びによっては、それよりも早い段階でソートが完了する場合があるのです。

ソートが完了したかどうかは、内側ループで隣接要素の交換が行われたかどうかで判断できます。つまり、外側のループが途中であっても、内側のループで１回も交換が行わなければ、ソートは完了しているということです。

ですので、内側ループ開始前に交換フラグを初期化し、交換が行われたらフラグを立て、内側ループ終了後にフラグを調べ、立っていなければ外側ループを終了させる、というようにすることで、早い段階でソートを完了させることができるわけです。

この「ソート完了の判断（＝ループを抜けるチャンス）」は外側ループで毎回発生しますので、外側ループの回数分（＝「要素数－１」回）あるというわけです。

お礼

お礼が大変遅くなってしまって申し訳ありません。

ありがとうございます。

なるほど！！と思いました。
そういう考え方をすればいいのですねー

本当に助かりました。ありがとうございます！！

回答No.4

imogasi

下記はエクセルＶＢＡですので、もしエクセルが使えれば
ツール－マクロ－ＶＢＥ－挿入－標準モジュールで出てくる画面に下記をコピー貼りつけして、Ｆ５キーを押して
実行してみて、Ｓｈｅｅｔ１を見てください。
隣接交換法を視覚化しようとしました。
Sub test01()
Cells.Clear
d = Array(11, 29, 32, 55, 60, 18, 46, 34, 17, 43)
k = 1
For i = 0 To 9
Cells(k, i + 1) = d(i)
Next i
k = k + 1
koukann = "y"
For j = 8 To 1 Step -1
If koukann = "n" Then Exit Sub
koukann = "n"
For i = 0 To j '列
'------前行データセット
For l = 0 To 9
Cells(k, l + 1) = Cells(k - 1, l + 1)
Next l
'------比較
If d(i) > d(i + 1) Then
Else
'----ＳＷＡＰ/交換
w = d(i)
d(i) = d(i + 1)
d(i + 1) = w
w = Cells(k, i + 1)
Cells(k, i + 1) = Cells(k, i + 2)
Cells(k, i + 1).Interior.ColorIndex = 6
Cells(k, i + 2) = w
Cells(k, i + 2).Interior.ColorIndex = 6
k = k + 1
koukann = "y"
End If
Next i
Cells(k - 1, i + 1).Interior.ColorIndex = 8
Next j
End Sub
--------
d = Array(11, 29, 32, 55, 60, 18, 46, 34, 17, 43)
の（）内の数字（文字列でも良い）を変えて実行して見てください。
黄色のセルが交換が行われたデータの場所でデータの移動の推移がヴィジュアルに一見出きるようにしました。
ライトブルーは位置が固まった場所段階を示します。
これをみて考える一助にしてください。

お礼

お礼が大変遅くなってしまって申し訳ありません。

ありがとうございます。
わざわざプログラムを組んでいただいてありがとうございます。

参考にさせていただいて、よく考えてみます。

回答No.2

ymmasayan

言われている意味がしっくりしませんが、次のようなヒントで出来ると思います。
ループは二重ループになります。
比較の順番は、1-2、2-3、3-4、4-5、5-6、6-7、7-8、8-9、9-10,
です。
これで10番目が確定しますので次のループは1回減ります。
1-2、2-3、3-4、4-5、5-6、6-7、7-8、8-9、
これの右端が一つずつ外れていって、最後に1-2の比較で終わりです。

お礼

お礼が大変遅くなってしまって申し訳ありません。

ありがとうございます。よく考えてみます。

回答No.1

edomin

「http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。」
どの辺が判らなかったのでしょう？
また、ご自分で考えられたアルゴリズムはどのような物ですか？

お礼

わざわざ補足を要求して下さったのに、返信が遅くて申し訳ありませんでした。
回答受付を締め切りさせていただきます。本当にごめんなさい。
ありがとうございます。

補足

返信が大変遅くなってしまって申し訳ありません。

>どの辺が判らなかったのでしょう？
ループを抜けるチャンスというのが、どこかわからなかったので。