-1

さまざまな並べ替えアルゴリズムが利用可能です。O(n^2) の時間計算量を持つソート アルゴリズムは、O(nlogn) よりも適している可能性があります。これは、インプレースまたは安定しているためです。例えば：

  • ある程度ソートされたものには、挿入ソートが適しています。
  • ほぼソートされた配列にクイックソートを適用するのはばかげています。
  • ヒープ ソートは O(nlogn) で有効ですが、安定していません。
  • マージソートは組み込みシステムでは使用できません。最悪の場合、O(n) のスペースの複雑さが必要になるためです。

どのソートアルゴリズムがどのような条件に適しているか知りたいです。

  • 名前をアルファベット順に並べ替えるのに最適な並べ替えアルゴリズムはどれですか?
  • より少ない整数をソートするのに最適なソートアルゴリズムはどれですか?
  • より少ない整数を並べ替えるのに最適な並べ替えアルゴリズムはどれですか?ただし、範囲が大きい場合があります (98767 – 6734784)?
  • 数十億の整数をソートするのに最適なソートアルゴリズムはどれですか?
  • 空間と時間の両方に制約がある組み込みシステムまたはリアルタイム システムでの並べ替えに最適な並べ替えアルゴリズムはどれですか?

これらのタイプの比較のために、これら/その他の状況、書籍、または Web サイトを提案してください。

4

2 に答える 2

2

特効薬はありませんが、いくつかの経験則があります。

  1. 基数ソート/カウントソートは通常、要素の範囲 ( とする)Uが要素の数 ( ) と比較して比較的小さいU<<n場合に適しています (ケース 2,4 に適合する可能性があります)。
  2. 挿入ソートは小さな (たとえばn<30) リストに適しており、O(nlogn)アルゴリズムよりも高速です (経験的に)。O(nlogn)実際、次の場合に挿入ソートに切り替えることで、トップダウン アルゴリズムを最適化できます。n<30
  3. 基数ソートのバリエーションも、文字列をアルファベット順にソートするのに適している場合があります。これはO(|S|*n)、通常の比較ベースのアルゴリズムがO(|S|*nlogn) [|S|文字列の長さ] であるためです。（あなたのケースに適合します1）
  4. ソートされた入力が非常に大きく、大きすぎてマージに収まらない場合、それを行う方法は外部ソートです。これはバリエーションまたはマージソートであり、ディスクの読み取り/書き込みの数を最小限に抑え、これらが順番に実行されるようにします- パフォーマンスが大幅に向上するためです。(ケース 4 に適合する可能性があります)
  5. 一般的なソートでは、クイック ソートと timsort (Java で使用) が優れたパフォーマンスを発揮します。
于 2012-12-15T08:01:04.307 に答える
0

マージソートは、最悪の場合、スペースの複雑さのO（n）を必要とするため、組み込みシステムでは使用できません。

stable_sortあなたはC++からの関数に興味があるかもしれません。通常のマージソートに余分なスペースを割り当てようとしますが、それが失敗した場合は、時間計算量が劣るインプレースの安定したマージソートを実行します（n * ((log n)^2)の代わりにn * (log n)）。C ++を読むことができれば、お気に入りの標準ライブラリの実装を見ることができます。そうでない場合は、言語に依存しない用語で説明されている詳細を見つけることができると思います。

インプレース安定ソート（特にインプレースマージ）に関する一連の学術文献があります。

したがって、C ++では、経験則は簡単です。「std::stable_sort安定したソートが必要な場合は使用し、それ以外の場合は使用しますstd::sort」。Pythonを使用すると、さらに簡単になります。経験則は「使用sorted」です。

一般に、多くの言語にはかなり巧妙なソートアルゴリズムが組み込まれており、ほとんどの場合それらを使用できます。標準ライブラリを打ち負かすために独自の実装が必要になることはめったにありません。独自に実装する必要がある場合は、教科書を取り出し、見つけられる限り多くのトリックを使用していくつかのアルゴリズムを実装し、心配している特定のケースについて互いにテストすることに代わるものはありません。あなたがライブラリ機能を打ち負かす必要があるために。

この質問に答えて期待するかもしれない「明白な」アドバイスのほとんどは、1つ以上の一般的なプログラミング言語の組み込みのソート関数にすでに組み込まれています。しかし、あなたの特定の質問に答えるために：

名前をアルファベット順に並べ替えるのに最適な並べ替えアルゴリズムはどれですか？

基数ソートは、C ++のような標準の比較ソートを排除sortする可能性がありますが、名前に「適切な」照合ルールを使用している場合は、それが不可能な場合があります。たとえば、「McAlister」は「MacAlister」と同じようにアルファベット順に並べられ、「St.John」は「SaintJohn」と同じようにアルファベット順に並べられていました。しかし、プログラマーがやって来て、多くの特別なルールをコーディングするのではなく、ASCII値で並べ替えたいと考えたため、ほとんどのコンピューターシステムはそれらのルールを使用しなくなりました。金曜日の午後はこの種の機能に適した時間だと思います;-)実際の名前ではなく、「正規化された」名前の文字で基数ソートを使用する場合でも、基数ソートを使用できます。

英語以外の言語での「適切な」照合規則も面白いです。たとえば、ドイツ語では、「Grüber」は「Grueber」のように並べ替えられるため、「Gruber」の後に「Gruhn」の前に表示されます。英語では「Llewellyn」という名前は「Lewis」にちなんでいますが、私はウェールズ語（まったく同じアルファベットを使用していますが、従来の照合規則が異なります）が前にあると信じています。

そのため、実際に行うよりも、文字列の並べ替えの最適化について話す方が簡単です。文字列を「適切に」ソートするには、ロケール固有の照合ルールをプラグインできる必要があります。比較ソートから離れると、すべての照合コードを書き直す必要がある場合があります。

より少ない整数をソートするのに最適なソートアルゴリズムはどれですか？

少数の小さな値の場合は、カウントソートかもしれませんが、データが十分に小さくなると（20〜30要素）挿入ソートに切り替えるイントロソートはかなり良いです。ティムソートは、データがランダムでない場合に特に適しています。

より少ない整数をソートするのに最適であるが、範囲が大きい（98767 – 6734784）ソートアルゴリズムはどれですか？

範囲が広いとソートのカウントが除外されるため、範囲の広い整数の数が少ない場合は、Introsort/Timsortを使用します。

数十億の整数を並べ替えるのに最適な並べ替えアルゴリズムはどれですか？

「数十億」とは「メモリに収まらないほど多すぎる」という意味の場合、ゲームが少し変わります。おそらく、データをメモリに収まるチャンクに分割し、Intro / Timでそれぞれをソートしてから、外部マージを実行する必要があります。32ビット整数をソートする64ビットマシンを使用している場合は、ソートをカウントすることを検討できます。

空間と時間の両方が制約となる組み込みシステムまたはリアルタイムシステムでの並べ替えに最適な並べ替えアルゴリズムはどれですか？

おそらくイントロソート。

ややソートされたものには、挿入ソートが適しています。

確かに、ティムソートは同じ状況を利用しています。

ほぼソートされた配列にクイックソートを適用するのは愚かです。

誤り。Hoareによって最初に公開されたプレーンなQuickSortを使用する人は誰もいません。「ソートされたデータ」よりもキラーケースをはるかに目立たなくする、より適切なピボットの選択を行うことができます。悪いケースに徹底的に対処するために、イントロソートがあります。

ヒープソートはO（nlogn）で適切ですが、安定していません。

本当ですが、イントロソートの方が優れています（また安定していません）。

マージソートは、最悪の場合、スペースの複雑さのO（n）を必要とするため、組み込みシステムでは使用できません。

これを処理するには、インプレースマージをやや遅くstd::stable_sortします。

于 2012-12-15T11:18:05.167 に答える