80

ティムソート（ウィキペディアによる）のパフォーマンスがはるかに優れているように見えるのに、クイックソートが全体的に最速のソートアルゴリズムであると私がよく耳にするのはなぜですか？グーグルはどんな種類の比較もしなかったようだ。

4

5 に答える 5

58

TimSortは高度に最適化されたマージソートであり、古いマージソートよりも安定していて高速です。

クイックソートと比較すると、2つの利点があります。

  1. ほぼソートされたデータシーケンス（逆ソートされたデータを含む）では信じられないほど高速です。
  2. 最悪の場合はまだO（N * LOG（N））です。

正直なところ、＃1が有利だとは思いませんが、感動しました。

クイックソートの利点は次のとおりです

  1. QuickSortは非常にシンプルで、高度に調整された実装でも、そのpseduoコードを20行以内に書き留めることができます。
  2. ほとんどの場合、QuickSortが最速です。
  3. メモリ消費量はLOG（N）です。

現在、Java 7 SDKは、ティムソートと新しいクイックソートバリアント、つまりDualPivotQuickSortを実装しています。

安定ソートが必要な場合は、ティムソートを試してください。それ以外の場合は、クイックソートから始めてください。

于 2013-10-25T10:25:14.210 に答える
27

多かれ少なかれ、それはティムソートがハイブリッドソートアルゴリズムであるという事実と関係があります。つまり、使用する2つの基本的なソート（マージソートと挿入ソート）は、多くの種類のデータに対してクイックソートよりも劣りますが、ティムソートはそれが有利な場合にのみそれらを使用します。

Patrick87が述べているように、少し深いレベルでは、クイックソートは最悪の場合のO（n 2）アルゴリズムです。適切なピボットを選択するのは難しいことではありませんが、O（n log n）クイックソートを保証すると、平均してソートが一般的に遅くなります。

ティムソートの詳細については、この回答とリンクされたブログ投稿を参照してください。基本的に、ほとんどのデータがすでに部分的にソートされていることを前提とし、mergesortを使用して効率的なマージを可能にするソートされたデータの「実行」を構築します。

于 2011-10-14T16:13:23.560 に答える
19

一般的に言えば、クイックソートはプリミティブ配列に最適なアルゴリズムです。これは、メモリの局所性とキャッシュが原因です。

JDK7は、オブジェクト配列にTimSortを使用します。オブジェクト配列は、オブジェクト参照のみを保持します。オブジェクト自体はヒープに格納されます。オブジェクトを比較するには、ヒープからオブジェクトを読み取る必要があります。これは、あるオブジェクトのヒープの一部から読み取り、次にヒープの別の部分からオブジェクトをランダムに読み取るようなものです。多くのキャッシュミスが発生します。このため、メモリの局所性はもはや重要ではないと思います。これが、JDKがプリミティブ配列の代わりにオブジェクト配列にTimSortのみを使用する理由である可能性があります。

これは私の推測です。

于 2014-11-17T02:01:40.230 に答える
5

これが私のマシンのベンチマーク番号です（i7-6700 CPU、3.4GHz、Ubuntu 16.04、gcc 5.4.0、パラメーター：SIZE=100000およびRUNS=3）：

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

ベンチマークは、Cでいくつかのソートアルゴリズムを実装したSwensonのソートプロジェクトからのものです。おそらく、彼の実装は代表的なものとして十分ですが、私はそれらを調査していません。

だからあなたは本当に言うことができません。ベンチマーク番号は最大2年間しか関連性がなく、その後は繰り返す必要があります。おそらく、2011年に質問があったときにティムソートがqsort waaayを打ち負かしましたが、時代は変わりました。または、qsortは常に最速でしたが、timsortはランダムでないデータでそれを打ち負かしました。または、スウェンソンのコードはそれほど良くなく、より優れたプログラマーはティムソートに有利に流れを変えるでしょう。あるいはCFLAGS、コードをコンパイルするときに、私は吸って、権利を使用しなかったのかもしれません。または...あなたはポイントを取得します。

于 2017-09-24T20:45:36.733 に答える
3

順序を保持する並べ替えが必要な場合、またはプリミティブ配列ではなく複雑な配列（ヒープベースのオブジェクトを比較する）を並べ替える場合は、TimSortが最適です。他の人が述べたように、クイックソートは、プリミティブ配列のデータとプロセッサキャッシングの局所性から大きな恩恵を受けています。

クイックソートの最悪のケースがO（n ^ 2）であるという事実が提起されました。幸い、クイックソートを使用すると、最悪の場合にO（n log n）時間を達成できます。クイックソートの最悪のケースは、ピボットが既にソートされた配列の最初または最後の要素である場合など、ピボットポイントが最小値または最大値のいずれかである場合に発生します。

ピボットを中央値に設定することで、O（n log n）の最悪の場合のクイックソートを実現できます。中央値を見つけることは線形時間O（n）で行うことができるので。O（n）+ O（n log n）= O（n log n）であるため、これが最悪の場合の時間計算量になります。

ただし、実際には、ほとんどの実装ではランダムピボットで十分であることがわかっているため、中央値を検索しないでください。

于 2019-09-27T04:07:11.250 に答える