No.1ベストアンサー
- 回答日時:
では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。
おおざっぱに言うと
まじめに比較すれば、
一つ目と残りn-1個の比較
2つ目とそれ以降のn-2個の比較
...
と、要素数nの二乗に比例した回数の比較必要です。これがバブルソートの計算量です。
これを、大きいもの方と小さい方の半分に分けてそれぞれを並び変えれば、
1つの並び換えが(n/2)の二乗= 1/4 * nの2乗
それが大と小の2回で * 2
合わせて 1/4 * nの2乗 * 2
= 1/2 * nの2乗
とバブルソートの半分になります。その半分のものを更に半分に...とやっていくと、最後には n * log2 n に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)
細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。
No.3
- 回答日時:
念のためですが....
#2 ではピボットの選び方として「普通は、最初の値や最後の値が使われる」と書かれていますが, これは「アルゴリズムの説明」としてはあり得ても (まあ「アルゴリズムの説明」で最後の値を使うのはかなりひねくれていますが) 「普通に使うため」にはあり得ません. その理由はまさに #2 に書いてある通り「整列されているものに対して適用するとO(n^2)」となってしまうからです. 普通に使うなら「データ列の中央の値を使う」とか「最初と中央と最後のうち真ん中の値のものを使う」とかの選び方をするはずです.
もっともどのような選び方においても「最悪のデータ列」というのは存在するので, 「ピボットの値をランダムに選ぶ」という投げやりな方法をすることもあります.
なお, 本題に対する「大雑把な説明」としては「どちらも一定の条件が成り立つときに 2つのデータの位置を入れ替えるんだけど, どことどこを入れ替えているのかを考えてみる」のがよいかと.
No.2
- 回答日時:
クイックソートはいい具合にランダムにデータが並んでいるという最良の場合にのみO(n log n)になり、整列されているものに対して適用するとO(n^2)です。
クイックソートの手順は、ピボットと呼ばれるデータをまだ大小に分けられていない場所から適当に選び(普通は、最初の値や最後の値が使われる)、それよりも大きい値と小さい値に残りを分け、分けられた中でまた同じ操作を繰り返すというものであるのはご存知かと思います。こうすると、ピボットよりも大きいものと小さいものに一度分けたら、大きいグループの要素と小さいグループの要素を今後は比較しません。つまり、それだけ比較の回数が減ります。バブルソートだとこういうグループ分けが無いので、毎ターン最小値or最大値を残りのグループから探すのに対し、クイックソートでは1/2の領域を更に大小に分けるだけで済みます。n個の要素が毎回綺麗に1/2ずつに分けられていくと、log n回分けることになると思いますが、そのたびに中に入っている要素を整理するのでおおよそ1/2ずつに分けたラウンドで合計n-1回、1/4ずつに分けたラウンドで合計n-3回、...と各ラウンドでざっくり言ってn回の比較が必要になります。よって、O(n log n)です。
...という説明でわかりましたでしょうか?
更にこの手の話を理解したい場合は、分割統治法について調べてみるとよいでしょう。分割統治法自体は、マキャベリの君主論にあるdivide et impera (分割して統治せよ) から来たと言われていますが。
同じく分割統治法のアルゴリズムでは、クイックソートよりはマージソートのほうがわかりやすいですね。クイックソートと違って毎回同じスピートで処理してくれる代わりに倍のメモリーが必要になりますが。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) エクセルのソート方法について 1 2023/01/13 00:01
- その他(プログラミング・Web制作) 機械語に詳しい方 2 2022/07/10 12:06
- 外国株 40年間の総資産の成長 5 2022/04/03 04:49
- 世界情勢 イーロン・マスクがツイートで警告、このままいけば「日本は消滅する」について 8 2022/05/09 14:30
- 数学 関数が単調増加かどうか調べる際に、微分をしてf'(x)>0だからf(x)は単調増加であるとした後に、 4 2023/04/15 00:52
- 経済学 ある経済の消費関数がC=a+c(Y−T)C=a+c(Y−T)の形で与えられている. ただし, a,c 1 2023/01/11 20:42
- YouTube 一昨日の夜中ぐらいから私の運営しているYoutubeチャンネルの様子がおかしいです。 1 2022/10/14 16:35
- 事件・犯罪 最近強盗が流行ってるような印象操作がされてると思っていたら、実際住宅侵入による強盗件数は増加してるよ 2 2023/02/22 08:56
- 弁護士・行政書士・司法書士・社会保険労務士 募集株式の発行 取締役会議事録について 募集事項 増加する資本金及び資本準備金に関する事項について 1 2022/06/06 01:25
- その他(インターネット接続・インフラ) 電話番号についてわかる方 1 2022/05/30 20:59
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語 exitの使い方
-
フォームを開くときに、コンボ...
-
足して100になるような乱数のア...
-
Excel-vba 文字列と変数を...
-
DWORDって
-
c言語で乱数を扱うときの
-
C#の問題で2つの整数a,bの...
-
vbaで極大値を抽出する方法
-
プラスの乱数の合計とマイナス...
-
乱数の初期化について
-
計算機イプシロン
-
c言語 偶数個
-
バブルソートとクイックソート
-
Excel VBAで値貼り付けのプログ...
-
DAOの操作をするとExceptionが...
-
数字の位ごとの値を表示するプ...
-
VBAで配列のNULL判定
-
何種類の値があるかを調べる方...
-
【C++/CLI】コンボボックスの値...
-
0~180まで0.0001刻みで乱数を...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語 exitの使い方
-
フォームを開くときに、コンボ...
-
Excel-vba 文字列と変数を...
-
数字の位ごとの値を表示するプ...
-
VB6.0-整数と余りを求める
-
VBAで配列のNULL判定
-
足して100になるような乱数のア...
-
フリーランタイマーの時間差分...
-
DataGridView 複数行同時変更...
-
相関係数p値の出し方
-
世界のナベアツ
-
10進数をアスキーコードに変換
-
C#で動的にコントロールを取得...
-
ラジオボタンの値の取得につい...
-
DWORDって
-
バッチファイルで正規表現を使...
-
4択問題のプログラムでランダム...
-
1つ前の値を変数に保存する方法
-
VBAの定数の使い方で、計算値を...
-
コンボボックスの名前を変数に...
おすすめ情報