![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e6f04cf)
隣接交換法(バブルソート)のアルゴリズムについて悩んでいます。
Q:配列「データ」には10個の要素があり、この配列「データ」を降順に並び替えるための隣接交換法アルゴリズムは?
一応、自分なりにアルゴリズムを考えたのですが、ループを抜けるチャンスが、【『要素』の数-1】回あるといわれ、それを考慮したアルゴリズムを考えよ、と言われました。
(そのチャンスというのが、どこにくるのかがわかりません。)
http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。
すみませんが、教えていただけないでしょうか?よろしくお願いします。
No.3ベストアンサー
- 回答日時:
正しく書かれたバブルソートは、「要素数-1」回の外側ループと、隣接要素の比較・交換を行う内側ループの二重ループ構造となります。
この二重ループが全て実行されればソートは完了するわけですが、元のデータの並びによっては、それよりも早い段階でソートが完了する場合があるのです。ソートが完了したかどうかは、内側ループで隣接要素の交換が行われたかどうかで判断できます。つまり、外側のループが途中であっても、内側のループで1回も交換が行わなければ、ソートは完了しているということです。
ですので、内側ループ開始前に交換フラグを初期化し、交換が行われたらフラグを立て、内側ループ終了後にフラグを調べ、立っていなければ外側ループを終了させる、というようにすることで、早い段階でソートを完了させることができるわけです。
この「ソート完了の判断(=ループを抜けるチャンス)」は外側ループで毎回発生しますので、外側ループの回数分(=「要素数-1」回)あるというわけです。
お礼が大変遅くなってしまって申し訳ありません。
ありがとうございます。
なるほど!!と思いました。
そういう考え方をすればいいのですねー
本当に助かりました。ありがとうございます!!
No.4
- 回答日時:
下記はエクセルVBAですので、もしエクセルが使えれば
ツール-マクロ-VBE-挿入-標準モジュールで出てくる画面に下記をコピー貼りつけして、F5キーを押して
実行してみて、Sheet1を見てください。
隣接交換法を視覚化しようとしました。
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
'----SWAP/交換
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.1
- 回答日時:
「
http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。」どの辺が判らなかったのでしょう?
また、ご自分で考えられたアルゴリズムはどのような物ですか?
この回答への補足
返信が大変遅くなってしまって申し訳ありません。
>どの辺が判らなかったのでしょう?
ループを抜けるチャンスというのが、どこかわからなかったので。
わざわざ補足を要求して下さったのに、返信が遅くて申し訳ありませんでした。
回答受付を締め切りさせていただきます。本当にごめんなさい。
ありがとうございます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 計算機科学 アルゴリズムについて 1 2023/01/01 19:43
- その他(プログラミング・Web制作) プログラミングの能力とアルゴリズムの能力は別物だと言われたのですが、これは本当ですか? プログラミン 1 2023/03/09 02:37
- その他(コンピューター・テクノロジー) アルゴリズム、配列のフローチャートの問題なのですが、全く分かりません… (ア)~(カ)に入るものを教 1 2023/06/29 21:19
- その他(プログラミング・Web制作) プログラミングって本来数学的な計算をする為のものではないのですか? 学校で配られたFortran90 11 2022/08/25 22:14
- 数学 M種類の部品からN種類の部品を抽出する効率的なアルゴリズム 2 2022/04/22 16:51
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 計算機科学 アルゴリズムが苦手な病気はあるの 私は、アルゴリズムの授業が苦手、あまりわかりません。また、本が4つ 2 2022/10/16 19:51
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
- その他(プログラミング・Web制作) プログラミング能力とアルゴリズム能力って違うのでしょうか? プログラミングの能力の一部にアルゴリズム 10 2023/03/31 14:34
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
UWSCの終了の仕方
-
VBAでの一時停止と再開の方法
-
画面を強制的に再描画させる方法
-
【VBA】全て空白のセルの列の非...
-
DoEventsが必要な理由について
-
範囲指定したセルを1つずつ飛...
-
フラグについて
-
For文を使った九九表の作成
-
素数の個数を求めるプログラミング
-
C#で別のフォームのprogress ba...
-
while(*s++=*t++)の判定は?
-
プログラミングについて。 1つ...
-
vbscriptでIE自動入力(途中で...
-
EXCEL VBA If~Else~構文の内容...
-
エディットボックスのテキスト...
-
pythonでリストの要素を小さい...
-
アクティブセルから、A列最終行...
-
StatementとResultSetのclose()...
-
アップルループについて
-
乱数の桁数指定、または範囲指定。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
プログラミングについて。 1つ...
-
画面を強制的に再描画させる方法
-
どなたかこのプログラミングを...
-
VBAでの一時停止と再開の方法
-
VBA for i=1 to lastrow
-
UWSCの終了の仕方
-
DoEventsが必要な理由について
-
エクセルの当番表を作っていま...
-
VBAで3秒だけ時間を止めたい
-
GIFアニメをループさせたくない
-
Escキーを押すと、中断する時と...
-
DOSコマンドのループ内のTIMEコ...
-
CSVファイルの特定の行だけを読...
-
アクティブセルから、A列最終行...
-
vb.netからエクセル関数書き込み
-
範囲指定したセルを1つずつ飛...
-
テキストボックスの名前に変数...
-
乱数の桁数指定、または範囲指定。
-
「偶数・奇数の和」のフローチ...
-
vbscriptでIE自動入力(途中で...
おすすめ情報