5

私は要素の配列を持っています。この配列は次のようになります。

  • ランダムにシャッフル (約 20% の確率)
  • 昇順でほぼソート* (約 40% の確率)
  • ほぼ降順でソートされます (約 40% の確率)

しかし、これらのケースのどれが当てはまるかは（事前に）わかりません。配列をすでに近い順序に並べ替えたいと思います。

出力が昇順か降順かは問題ではありませんが、どちらか一方でなければなりません (したがって、バイナリ検索を実行できます)。

ソートは安定している必要はありません。

背景情報: プロセスはおおまかに次のようになります。

  • 配列にデータを入力する
  • いくつかの属性 A で並べ替える
  • いくつかの処理を行います (変位値の計算、およびその他のマイナーなもの)
  • 他の属性 B で並べ替える
  • より多くの処理を行う
  • 属性 C でソート
  • より多くの処理を行う

A と B はしばしば相互に相関します (ただし、正または負の場合もあります)。B と C にも同じことが当てはまります。A == C の場合もあります。

* ここでの「ほぼソート」とは、ほとんどの要素が最終的な位置に近いことを意味します。しかし、それらの最終位置が正確であることはめったにありません (多くの付加的なノイズがあり、長くソートされたサブシーケンスはあまりありません)。次の並べ替え。 

昇順と降順を優先しないという事実を利用して、より安価にソートできるアルゴリズムはありますか (現在使用している TimSort と比較して?)

4

2 に答える 2

3

私は引き続き Timsort を使用します (ただし、代わりにSmoothsort *を使用することをお勧めします) が、まず配列を調べて、昇順または降順のどちらで並べ替えるかを決定します。最初と最後の要素を見て、それに応じて並べ替えます。配列がソートされていない場合、選択は重要ではありません。（部分的に）ソートされている場合、広い間隔でプローブすると、どちらの方法でも正しく検出される可能性が高くなります。

* Smoothsort は、Timsort と同じ最高、平均、および最悪のケースの時間と、より優れた空間の複雑さを持ちます。Timsort と同様に、部分的にソートされたデータを利用するように特別に設計されています。

于 2012-11-03T23:17:12.163 に答える
2

考慮すべき別の可能性：

  • （手巻き）インサートソートを開始
  • あなたが行っているように、あなたが実行した反転の数を数えます
  • いくつかの一定数の挿入を行った後、数えた反転の数を、最初にデータが逆に並べ替えられた場合にその時点までに発生したであろう反転の最大数と比較します。
  • 割合が 0 に近い場合、(おそらく) データはほぼ並べ替えられています。挿入ソートを完了します。これは、ほぼソートされたデータに対して非常に優れたパフォーマンスを発揮します。「おそらく」という音が気に入らない場合は、反転をカウントし続け、しきい値を下回った場合に Timsort にフォールバックする準備をしてください。
  • 比率が 1 に近い場合、(おそらく) データはほぼ逆に並べ替えられており、最初に少数の並べ替えられた要素があります。それらを最後に移動し、逆にして、逆コンパレータで挿入ソートを完了します。
  • それ以外の場合、データはランダムです。お気に入りの並べ替えアルゴリズムを使用してください。私は Timsort と言いますが、それはほぼソートされたデータでうまく機能するため、Timsort が均一にシャッフルされたデータで行うよりも少なくともわずかに優れたアルゴリズムが他にあるに違いありません。おそらくティムなしの単純なマージソート。

「小さな固定数」は、悪い場合でも挿入ソートがかなり高速な数になる可能性があります。10～20くらいだと思います。任意の数の挿入と "0/1 に近い" という任意のしきい値について、一様にシャッフルされたデータで偽陽性の確率を計算することは可能ですが、私は怠惰です。

最初と最後のいくつかの配列要素は通常、傾向に逆らうと言います。その場合、それらを最初のテスト挿入ソートから除外できます。

明らかに、このアプローチは Timsort にいくらか影響を受けています。しかし、Timsort は、実行を含むデータに対して非常に最適化されています。私は、1 回の大きな実行に近いデータ (いずれかの方向) に対してのみ、非常に最適化しようとしました。Timsort のもう 1 つの特徴は、十分にテストされていることです。それを共有するつもりはありません。

于 2012-11-03T23:35:17.020 に答える