0

この質問は、ほとんどが並べ替えられたデータに対してどの並べ替えアルゴリズムが最適に機能するか? に関連しています。

違いは、他にも非常に重要な制限があることです。値は、並べ替えごとに少量ずつ変更されます。

これは、ベクトルがほぼソートされたままであり、変位した値がほぼその位置にあることを意味します。いくつかのテストを行った後、同じ答えが私の場合に当てはまるようです。

この場合により良いかもしれない他のアルゴリズムを知っていますか?

4

5 に答える 5

1

ティムソートまたはスムースソートを検討してください。これらは、主にソートされたデータを念頭に置いて設計されています。

于 2012-08-17T16:09:55.157 に答える
0

すべてのペアa[i]<= a [i+1]を比較します。これがfalseの場合、2番目の要素を新しい配列に移動します。

新しい配列（mergesort、heapsort、またはその他のO（n * log n）アルゴリズム）を並べ替えて、新しい配列と古い配列を再度マージします。

于 2012-08-17T17:51:13.750 に答える
0

更新が頻繁に行われる場合は、ベクターを何度もソートするよりも、インデックス構造 (つまり、二分探索木) を維持する方がよいでしょう。

于 2012-08-17T06:37:40.117 に答える
0

Insertion-Sort と Bubble-Sort はどちらも、入力に対して線形の最良のケースの複雑さを持ち、既に並べ替えられています (値が連続的に変化しているため、これは最適です。つまり、入力ベクトルの各要素を確認する必要があります)。安定しています（問題の説明を考えると、これは便利なプロパティのようです）。

于 2012-08-17T10:14:29.253 に答える
0

これはどう：

Def CheckedMergeSort(L)

    Count = 0
    S(1) = 0

    For I in 2 to |L|
       If (L(I-1) < L(I))
           Count = Count + 1
           S(I) = Count

    Def MergeSort(A, B)
        If (A != B and S(B)-S(A) != B-A)
            C = (B + A) / 2
            MergeSort(A,C)
            MergeSort(C+1,B)
            InplaceMerge(L(A..C), L(C+1..B))

    MergeSort(1, |L|)

S(i) を埋めるために、入力の線形時間プリパスが行われます。これは、i より前にソートされた順序でいくつのペアがあったかを追跡します。

次に、2 つの境界 S(j)-S(i) を減算し、それを j-1 と比較することにより、サブシーケンス L(i..j) がソートされた順序であるかどうかを判断できます。

マージソートは、再帰で見つかったソートされたシーケンスを一定時間でスキップできます。

(たとえば、配列がエントリでソートされている場合、MergeSort(1, |L|) は noop になります。)

于 2012-08-17T18:14:33.157 に答える