OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

それぞれのソート方法の特徴の違いについて

  • 困ってます
  • 質問No.210663
  • 閲覧数445
  • ありがとう数3
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 58% (18/31)

ソートを勉強しているのですが、
ヒープソートや、クイックソートなど効率の良いやり方と、
バブルソートのように、そうでないものがあるらしいことを
知ったのですが、最強のアルゴリズムは存在するのですか?
それとも、ソート対象の状況によって、有効なアルゴリズムが違ってくるのですか? もし違うとしたら、どのように違うのでしょうか。
通報する
  • 回答数4
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.4

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

その他の回答 (全3件)

  • 回答No.1
レベル9

ベストアンサー率 11% (18/153)

「アルゴリズ○とデータ構造」 近藤嘉○ SOFTBA○K という本に、わかりやすく解説してありますよ。 本の内容を書いたら、著作権の侵害になるので説明できませんが、使用するソートを選ぶときは、「時間(ソートの速さ)と空間(メモリの使用量)のトレードオフ(どっちをとるか)」です。 ...続きを読む
「アルゴリズ○とデータ構造」 近藤嘉○ SOFTBA○K
という本に、わかりやすく解説してありますよ。

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

お礼率 58% (18/31)

本のご紹介ありがとうございます。今度読みたいです。
メモリの使用量による選択もあるのだとは知りませんでした。
どうもありがとうございました。
投稿日時 - 2002-02-03 21:58:57


  • 回答No.2
レベル13

ベストアンサー率 34% (574/1662)

用途によりますので、最強は存在しないといっていいと思います。 速度とメモリの使用量だけでなく、他にも見当すべき項目はあります。 例えば、マージソートというメモリの乗らないサイズの出たを高速にソートするというものもあります。 また、速度も条件によって変化します。 例えばヒープソートはどういうデータが入力であっても安定した速度が出ますが、 クイックソートは入力のデータの並びによっては、 ...続きを読む
用途によりますので、最強は存在しないといっていいと思います。


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

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

他にもいろいろありますが、結局は入力のデータの量や、性質、必要とする速度、手間等で
最適なソートは異なります。
お礼コメント
accessdb_user

お礼率 58% (18/31)

ありがとうございます。とてもためになりました。
昔ヒープソートやクイックソートを習ったのですが、今では、わかりません。
要素が少なかったら、バブルソートの方がいいのですね。
今、バブルソートしかかけないので、安心しました。
投稿日時 - 2002-02-03 22:09:49
  • 回答No.3

大抵のアルゴリズムの速度はデータの交換(移動)回数に比例します。それぞれのアルゴリズムの平均交換回数や最大交換回数になるソート対象の状態を考慮して使い分ける事になると思います。あらゆる条件で交換回数が最小になるアルゴリズムはありません。IOが発生するならば、さらに複雑になります。 例えば、1000個のランダムに並んだデータをソートさせる場合と、900個のソートされたデータに100個のランダムに並んだ ...続きを読む
大抵のアルゴリズムの速度はデータの交換(移動)回数に比例します。それぞれのアルゴリズムの平均交換回数や最大交換回数になるソート対象の状態を考慮して使い分ける事になると思います。あらゆる条件で交換回数が最小になるアルゴリズムはありません。IOが発生するならば、さらに複雑になります。

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

お礼率 58% (18/31)

どうもありがとうございます。1000個のランダムに並んだデータをソートさせる場合と、900個のソートされたデータに100個のランダムに並んだデータを追加してソートさせる場合、という論点と同様なことを私も想像していました。アクセスのオートナンバがところどころだけ、乱れてしまっている場合とか・・。
ところで、IOとは何でしょうか。
投稿日時 - 2002-02-03 22:10:44
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ