ソートを勉強しているのですが、
ヒープソートや、クイックソートなど効率の良いやり方と、
バブルソートのように、そうでないものがあるらしいことを
知ったのですが、最強のアルゴリズムは存在するのですか?
それとも、ソート対象の状況によって、有効なアルゴリズムが違ってくるのですか? もし違うとしたら、どのように違うのでしょうか。

このQ&Aに関連する最新のQ&A

A 回答 (4件)

>ところで、IOとは何でしょうか。


すいません。これは、I/O と書くべきでした。
つまり、ソートの対象が比較的大きい場合、最初からディスクアクセスを前提としたり、スワップが発生する可能性がある事を考慮する事もあると言いたかったのですが、ちょっと余計な事でした。
    • good
    • 0

大抵のアルゴリズムの速度はデータの交換(移動)回数に比例します。

それぞれのアルゴリズムの平均交換回数や最大交換回数になるソート対象の状態を考慮して使い分ける事になると思います。あらゆる条件で交換回数が最小になるアルゴリズムはありません。IOが発生するならば、さらに複雑になります。

例えば、1000個のランダムに並んだデータをソートさせる場合と、900個のソートされたデータに100個のランダムに並んだデータを追加してソートさせる場合では、選択するアルゴリズムが変わってくるような気がしませんか?

この回答への補足

どうもありがとうございます。1000個のランダムに並んだデータをソートさせる場合と、900個のソートされたデータに100個のランダムに並んだデータを追加してソートさせる場合、という論点と同様なことを私も想像していました。アクセスのオートナンバがところどころだけ、乱れてしまっている場合とか・・。
ところで、IOとは何でしょうか。

補足日時:2002/02/03 22:10
    • good
    • 0

用途によりますので、最強は存在しないといっていいと思います。




速度とメモリの使用量だけでなく、他にも見当すべき項目はあります。
例えば、マージソートというメモリの乗らないサイズの出たを高速にソートするというものもあります。

また、速度も条件によって変化します。
例えばヒープソートはどういうデータが入力であっても安定した速度が出ますが、
クイックソートは入力のデータの並びによっては、
極端に性能がおちます。
また、データ数が極端に少ない場合は、アルゴリズムが複雑なヒープソート、クイックソートは単純なアルゴリズムのソートに速度でまけますし、
つくるのも面倒です(^^;

他にもいろいろありますが、結局は入力のデータの量や、性質、必要とする速度、手間等で
最適なソートは異なります。
    • good
    • 0
この回答へのお礼

ありがとうございます。とてもためになりました。
昔ヒープソートやクイックソートを習ったのですが、今では、わかりません。
要素が少なかったら、バブルソートの方がいいのですね。
今、バブルソートしかかけないので、安心しました。

お礼日時:2002/02/03 22:09

「アルゴリズ○とデータ構造」 近藤嘉○ SOFTBA○K


という本に、わかりやすく解説してありますよ。

本の内容を書いたら、著作権の侵害になるので説明できませんが、使用するソートを選ぶときは、「時間(ソートの速さ)と空間(メモリの使用量)のトレードオフ(どっちをとるか)」です。
    • good
    • 0
この回答へのお礼

本のご紹介ありがとうございます。今度読みたいです。
メモリの使用量による選択もあるのだとは知りませんでした。
どうもありがとうございました。

お礼日時:2002/02/03 21:58

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q化合物の同義語について

こんにちは。製薬企業の特許関係の仕事をしています。
仕事上、多量の文献を調査するのですが、その際同義語も含めて調査する必要があります。この、同義語を調べるのに苦労しています。
同義語を調べるのに便利な本、又はWEBページはありますでしょうか?
どなたか知っていたら教えてください。

宜しくお願い致します。

Aベストアンサー

こちらで引いてみたら,うまくいくかもしれません.
http://homepage1.nifty.com/k_funa/aiueo2.html

他にも,便利な情報がこちらに出ています.
http://www.chem-station.com/
http://chemnews.cambridgesoft.com/index.cfm?language=j

Qバブルソートとクイックソート

まだソートについて勉強し始めたばかりですが
バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し
クイックソートはそれほど増加しないのはなぜでしょうか??
検索してみてもプログラムが書いてあってよくわからないので...

根本的なところなのでしょうがどなたか教えてください!

Aベストアンサー

では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。

おおざっぱに言うと

まじめに比較すれば、
一つ目と残り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 に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)

細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。

Qロッケン・ベーレン・アウスレーゼと貴腐ワイントは同義語ですか?

ドイツ・ワインの分類/等級の説明で、しばしば「トロッケン・ベーレン・アウスレーゼ(貴腐ワイン)」の如く、両者が同義語であると受け取れる解説を見かけますが、両者は厳密な定義上も100%同義語なのでしょうか?
若しも何らかの差異があるならば、違いを解説戴ければ幸いです。

Aベストアンサー

「称号付き上級ワイン」と訳される最上級クラスは、次の6つです。
肩書きはブドウの糖度で決まります。

「トロッケンベーレンアウスレーゼ」は、「貴腐菌がついて干しブドウ状になったブドウ粒から造る最高級の極甘口ワイン」と一般的に解されますが、意味は、「乾いた果粒を選り摘んだ」ということで、必ずしも貴腐ワインということではありません。
たいていのブドウ品種は、貴腐化なくして高糖度にはできないと言われていますが、ごく限られた品種では、貴腐によらずして比較的容易に高糖度に達することができます。
トロッケンというのは、干からびている、という意味です。
但し、単に“トロッケン”と表示されているものは、「辛口」という意味なので注意が必要です。


「アイスヴァイン」は、樹の上で完熟し、凍りついたブドウから造る甘口ワイン。

「ベーレンアウスレーゼ」は、過熟したブドウ粒から造る極甘口ワインですが、貴腐ブドウもブレンドされます。

「アウスレーゼ」は、よく熟したブドウ房から造るワイン。

「シュペトレーゼ」は、通常よりも7日以上遅摘みのブドウから造るワイン。

「カビネット」は、普通のブドウから造るワインで、最も辛口&低アルコール。

「称号付き上級ワイン」と訳される最上級クラスは、次の6つです。
肩書きはブドウの糖度で決まります。

「トロッケンベーレンアウスレーゼ」は、「貴腐菌がついて干しブドウ状になったブドウ粒から造る最高級の極甘口ワイン」と一般的に解されますが、意味は、「乾いた果粒を選り摘んだ」ということで、必ずしも貴腐ワインということではありません。
たいていのブドウ品種は、貴腐化なくして高糖度にはできないと言われていますが、ごく限られた品種では、貴腐によらずして比較的容易に高糖度に達すること...続きを読む

Qクイックソートのアルゴリズムについて

(1)クイックソートが使われるのは実際にはどのような場面なのでしょうか?メインメモリで使われていると聞きましたが‥
(2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか?
(3)マージソートはどのような局面で使われるのでしょうか?

Aベストアンサー

 #1です。再登場。

>具体的にはどんなデータを扱っているのでしょうか?
 SQLのエンジンです。フリーで出してるんです。
 どんなデータが来るか予測できないので、ソート方式の選定には苦労した記憶があります。
 ちなみに、自分なりに実験した結果、俺が使ってるp-マージソートは、クイックソートと比べても遅延は少ししかないみたいです。

Qhappen to meetの同義語

happen to meetの同義語

こんにちは。

run to, run into, take to, come forが選択肢としてあります。

happen to meetは偶然会う、出くわすみたいな意味なのですが、上記の中で同義語はどれでしょうか?

力を貸して頂けるとありがたいです。

Aベストアンサー

run to
http://eow.alc.co.jp/run+to/UTF-8/?ref=sa

run into
http://eow.alc.co.jp/run+into/UTF-8/

take to
http://eow.alc.co.jp/take+to/UTF-8/

come for
http://eow.alc.co.jp/come+for/UTF-8/

さあ、一体どれでしょうか?

QC言語 クイックソートのアルゴリズム

クイックソートのプログラムを以下のように書くべきところを
     ・・・
int bin_sort(int array[],int l,int r)
{
・・・
pivot=array[(l+r)/2];
・・・

while(1)
{
  while(array[i]<pivot)
i++;
while(array[j]>pivot)
j--;
・・・
以下のようにしたところ正しくソートされません。
理由が良く解りません。
int bin_sort(int array[],int l,int r)

    ・・・
  pivot=(l+r)/2; 
・・・

while(1)
{
while(array[i]<array[pivot])
i++;
while(array[j]>array[pivot])
j--; 
・・・
どうか宜しくお願いします。

クイックソートのプログラムを以下のように書くべきところを
     ・・・
int bin_sort(int array[],int l,int r)
{
・・・
pivot=array[(l+r)/2];
・・・

while(1)
{
  while(array[i]<pivot)
i++;
while(array[j]>pivot)
j--;
・・・
以下のようにしたところ正しくソートされません。
理由が良く解りません。
int bin_sort(int array[],int l,int r)

    ・・・
  pivot=...続きを読む

Aベストアンサー

array[]内のデータがソート処理により入れ替わってしまう
ので、基準値の array[pivot]の値が変わってしまうから。

Q思惑 動作 行動 感情 形式 の同義語か対義語

この5つの言葉のうち
同義語、もしくは対義語になる言葉は
行動と形式(対義語)になるのでしょうか。
分かる方、教えて下さい。

Aベストアンサー

#1の者です。
私は
反対の意味を持つ語=対義語
同じ意味を持つ語=同義語
のつもりでお答えしたのですが、


>「形式に囚われず、行動しろ」

この文の場合、形式=きまりごと、型。という意味になりますよね。で、「形式に囚われず」とは、行動する際の条件として使われていますね。
とすると「行動」は形式の反対の意味にはなり得ません。例えば「遊ばず、勉強しろ」という文ならば、「遊ぶ」と「勉強する」が反対の意味でしょうけど、前の文ではそのような関係ではないでしょう?

よって、もし私に『「思惑 動作 行動 感情 形式」このうち同義語か反対語の関係にある二語を指摘せよ』と出題されたとしたら、「正解なし」と解答します。

試験に出題されたということですが、どのような試験かは存じませんが、あまりお気になさらなくてもいいのではないでしょうか?どのような結果になるにせよ、過ぎたことよりもその先でどう対処するか、が大切だと思いますよ(偉そうですが)。

QCのバブルソートに関する問題(超初級らしい)

int型配列{10,4,7,50,48,3}を昇順に並べて、順に標準出力しなさい

という問題を出されたのですが、今日はじめてC言語に(プログラミング自体はじめて)触れた私にとっては、まったくわからない問題です。

実行結果は



10
48
50
になるらしいのですが、どのようにプログラムを書いたらよいのかさっぱりわかりません。
どなたかご指導いただけたら幸いです。よろしくお願いします。

Aベストアンサー

参考にしてください。

参考URL:http://www.geocities.co.jp/SiliconValley-Oakland/1680/zsaru/zsaru07.html

Q英語で日本語の「同義語」はなんといいますか?

英語で日本語の「同義語」はなんといいますか?

Aベストアンサー

synonymです。
http://www.synonym.com/synonyms/

Q挿入ソートとバブルソート

挿入ソートとバブルソートについて教えてください。どのようなアルゴリズムでソートされるのでしょうか?

Aベストアンサー

下記のページが参考になりませんか。

C言語によるアルゴリズム(コメント付き)http://www.sra.co.jp/people/miyata/algorithm/

並べ換えの問題
 http://www.cs.u-gakugei.ac.jp/~miyadera/Education/Lecture/ElecBook2/ptech17.htm


人気Q&Aランキング