バブルソートのアルゴリズムについて悩んでいます
- 配列「データ」を降順に並び替えるための隣接交換法アルゴリズムについて教えてください
- 要素の数-1回のループを抜けるチャンスがあるが、どこにくるのかわかりません
- バブルソートのアルゴリズムについては参照したサイトがわかりにくく、教えていただけませんか?
- ベストアンサー
隣接交換法のアルゴリズムについて
隣接交換法(バブルソート)のアルゴリズムについて悩んでいます。 Q:配列「データ」には10個の要素があり、この配列「データ」を降順に並び替えるための隣接交換法アルゴリズムは? 一応、自分なりにアルゴリズムを考えたのですが、ループを抜けるチャンスが、【『要素』の数-1】回あるといわれ、それを考慮したアルゴリズムを考えよ、と言われました。 (そのチャンスというのが、どこにくるのかがわかりません。) http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。 すみませんが、教えていただけないでしょうか?よろしくお願いします。
- straw1492
- お礼率100% (9/9)
- その他(プログラミング・開発)
- 回答数4
- ありがとう数6
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
正しく書かれたバブルソートは、「要素数-1」回の外側ループと、隣接要素の比較・交換を行う内側ループの二重ループ構造となります。この二重ループが全て実行されればソートは完了するわけですが、元のデータの並びによっては、それよりも早い段階でソートが完了する場合があるのです。 ソートが完了したかどうかは、内側ループで隣接要素の交換が行われたかどうかで判断できます。つまり、外側のループが途中であっても、内側のループで1回も交換が行わなければ、ソートは完了しているということです。 ですので、内側ループ開始前に交換フラグを初期化し、交換が行われたらフラグを立て、内側ループ終了後にフラグを調べ、立っていなければ外側ループを終了させる、というようにすることで、早い段階でソートを完了させることができるわけです。 この「ソート完了の判断(=ループを抜けるチャンス)」は外側ループで毎回発生しますので、外側ループの回数分(=「要素数-1」回)あるというわけです。
その他の回答 (3)
- imogasi
- ベストアンサー率27% (4737/17068)
下記はエクセル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) の()内の数字(文字列でも良い)を変えて実行して見てください。 黄色のセルが交換が行われたデータの場所でデータの移動の推移がヴィジュアルに一見出きるようにしました。 ライトブルーは位置が固まった場所段階を示します。 これをみて考える一助にしてください。
お礼
お礼が大変遅くなってしまって申し訳ありません。 ありがとうございます。 わざわざプログラムを組んでいただいてありがとうございます。 参考にさせていただいて、よく考えてみます。
- ymmasayan
- ベストアンサー率30% (2593/8599)
言われている意味がしっくりしませんが、次のようなヒントで出来ると思います。 ループは二重ループになります。 比較の順番は、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の比較で終わりです。
お礼
お礼が大変遅くなってしまって申し訳ありません。 ありがとうございます。よく考えてみます。
- edomin
- ベストアンサー率32% (327/1003)
「http://oshiete1.goo.ne.jp/kotaeru.php3?q=290051も参照しましたが、よくわかりません。」 どの辺が判らなかったのでしょう? また、ご自分で考えられたアルゴリズムはどのような物ですか?
お礼
わざわざ補足を要求して下さったのに、返信が遅くて申し訳ありませんでした。 回答受付を締め切りさせていただきます。本当にごめんなさい。 ありがとうございます。
補足
返信が大変遅くなってしまって申し訳ありません。 >どの辺が判らなかったのでしょう? ループを抜けるチャンスというのが、どこかわからなかったので。
関連するQ&A
- 乱数の順位付けのアルゴリズム
[0,1]の範囲で乱数を1000個、配列に発生させて、小さいもの100個を選び出すアルゴリズムということを考えます(知りたいのは数値と配列番号、むしろ配列番号が大事)。まず想定できるのはソートですが、それにもいろんなものがあり、クイックソート、バブルソートなどが挙げられます。ソートのアルゴリズムは既に開発されつくしたのかもしれませんが、どのようになっているでしょうか。一番高速な(かつ間違いない)な方法が1つあればそれを採用したいのですが。 そして1つ厄介なのですが、そのトップ100個以外の900個はソートする必要がないということです。私が考えているアルゴリズムは、 1.既に100個の選ばれていると仮定(初期はすべて1) 2.新しい1個が来たとき、100個の最低値よりも小さいなら考慮の対象なのだから最低値を交換してその100個でソートする。そうでない場合は何もしない。 3.次の新しい1個を調べて、項目2をする。 4.発生させた1000個でそれを繰り返す。 このアルゴリズムだと100個のソートを何百回かぐらいやることになります。 これをするぐらいだったら1000個のソートを1回やればいいということになるでしょうか(不必要な残りの900個もソートされてしまう)。あるいはその1回の1000個のソートの中でやる必要のない処理を排除する工夫があるかもしれません。 問題が難しくなく、素人っぽくコード化できると思いますが、その分、非効率なところも放置されそうなので高速化できるコードの書き方があったら教えて頂きたいのですが。コードというよりアイディアだけ説明していただいても助かります。実際はフォートランになると思いますが。よろしくお願いします。
- 締切済み
- C・C++・C#
- アルゴリズム
クイックソートは最初から配列変数が降順に並んでいる場合に遅くなる。この解決策を考えて説明せよ。また、うまくいく理由を述べよ。要素数nの配列変数を整列する場合 主語と述語があって、マル(。)で終わる文を複数書くこと。 キーワードの羅列、体言止めはNG 「解決策」と「うまくいく理由」を説明する。 よろしくおねがいします。
- 締切済み
- その他(学問・教育)
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか?」の第5章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)~(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
- クイックソートしながら重複要素削除アルゴリズム
アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ ている物が多く処理のイメージが沸かずクイックソートもコピペや既存 の関数で処理していて、満足に理解出来ていないのですが。 以下の問題を、お解かりになるかた教えて頂けませんでしょうか? ■問題 2万件位の数値データの中から重複要素を削除しながら昇順または降順で、 ソートするアルゴリズム(※1) ■条件 BASIC的(※2)な記述やプログラム中のコメントなどの形式でも構いま せん出来るだけ簡単に示して頂けると助かります。 補足 (※1)ソートする際、重複要素を消すともっと処理が早くなるのではと 思ったので。 目的は、処理の速さを求める事と、次回から応用が聞くよ うにソート自体を理解したいのでクイックソートで無くても構いません。 (※2)実際に動かなくても構いません、イメージが掴みやすい方が良いと いう意味でとって下さい。
- ベストアンサー
- その他(プログラミング・開発)
- modified bubble sort
ソーティングについて教えてください. ソーティングの手法に,バブルソートというものがあります(隣接するふたつを入れ替える).このソーティングでは,最大交換回数は要素数が n のとき, n(n-1)/2 となります. 隣接する要素の交換に加え,先頭と最後の要素の入れ替えも可能だとすると(イメージとしては,サイクリックなバブルソートです),最大交換回数は n^2/4 となるそうです. この n^2/4 になる,という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます).どなたかご教授頂ければと思います.
- 締切済み
- 数学・算数
- アルゴリズムの問題です
以下のフローチャートは、基本選択法でデータを昇順(小→大)にソートしたものなのですが、整数の一次元配列に格納されているデータ(100個)を降順(大→小)にソートするフローチャートを作成するには、どこの部分を変化させればいいのか教えていただけませんか? 手書きなので見にくいですがよろしくお願いします。 開始 l 整数配列A(100)と整数変数I,J,N,P,MIN,TEMPを宣言 l データの個数N の値を読む l ループ1の開始 I = 1,2,3, ・・・,N l A(I)の値を読む l ループ1の終了 l ループ2の開始 I = 1,2,3, ・・・,N l A(I)の値を出力 l ループ2の終了 l ループ3の開始 I = 1,2,3, ・・・,N-1 l MIN = A(I) l P = I l ループ4の開始 J = I+1,I+2,I+3, ・・・,N l l yes A(J) < MIN ーーーーーー MIN = A(J) l no l l P = J l l l←ーーーーーーーーーーー l ループ4の終了 l TEMP = A(I) l A(I) = A(P) l A(P) = TEMP l ループ3の終了 l ループ5の開始 I = 1,2,3, ・・・,N l A(I)の値を出力 l ループ5の終了 l 終了
- ベストアンサー
- その他([技術者向] コンピューター)
- バブルソートの実行時間について
バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。 バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。 なぜこのようになるのですか? よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 大滝みや子先生の「アルゴリズム解法」で
大滝みや子先生の 基本情報技術者 「かんたんアルゴリズム解法」流れ図と擬似言語で ページ49 第2章 基本例題 第1部アルゴリズムと流れ図 5 1次元配列へのデータ格納 の 表2で、 umaxnの要素"4"と"5" 及び statusの要素"空き"が ○(まる)で囲まれている理由が、解りません。 ご存知の方、教えて下さい。 宜しくお願いします。
- ベストアンサー
- その他(プログラミング・開発)
お礼
お礼が大変遅くなってしまって申し訳ありません。 ありがとうございます。 なるほど!!と思いました。 そういう考え方をすればいいのですねー 本当に助かりました。ありがとうございます!!