安定した並べ替えが大きな違いをもたらす実例（またはいくつかのビジネスユースケース）

Question

安定した並べ替えが大きな影響を与えるシナリオを知りたい。 JAVAの

以前のバージョンでは、クイックソートを使用したのArray.sortためながら、安定ソートであるcollections.sor APIの並べ替えをマージしました。 Javaの現在のバージョンではTim Sortが使用されています。 最近、Python、Java、Scalaなどの人気のある言語のほとんどがTim Sortを使用しています。ティム・ソートの使い方が安定しているかどうか分かります。 安定したソート手法を使用する強い動機は何ですか？安定ソートで

Answer 1

、データセットは、最も重要なのものから大幅に、一度に一つのフィールドでソートすることができます。たとえば、一部のスプレッドシートプログラムでは、一度に3フィールドずつ並べ替えることができません。スプレッドシートのソートは安定しているので、6つのフィールドソートが可能です。まず、3つの最下位フィールドでソートし、3つの最も重要なフィールドでソートします。元の順序を保持することは、望ましい副作用である可能性があります。データセットが名前でソートされ、そのデータセットのコピーが生年月日でソートされ、同じ生年月日の要素は、複雑な比較の必要なしに元の名前の順序を保持します。

もマージソート対クイックソートのパフォーマンスの問題があります。通常、マージソートではより多くの移動が行われますが、比較は少なくなります。比較オーバーヘッドが移動オーバーヘッドより大きい場合、マージソートは高速です。たとえば、オブジェクトへのポインタの配列（Javaがオブジェクトの配列を実装する方法）を並べ替えると、移動されるものがポインタであり、比較対象がオブジェクトであるため、マージソートが高速になります。