追加の配列を使用せずにマージソートの実装？

StackOverflow https://stackoverflow.com/questions/2171517

  •  24-09-2019
  •  | 
  •  

質問

私は最近、マージソートについて多くを読んだし、少なくとも1つの追加のアレイを使用せずにマージを行う方法があるのだろうか。それは可能でしょうか？

役に立ちましたか？

解決

ウィキペディアにそれが実際に可能であるが、任意のパフォーマンスの向上が得られない可能性がありますによると：

  ソートはその場で可能である（例えば、配列ではなく、リストを使用して）が、非常に複雑であり、かつ、実際にはほとんどないパフォーマンスの向上を提供する場合でもOにおけるアルゴリズムの実行（のN のログ< em>のN の）時間。これらのケースでは、ヒープソートのようなアルゴリズムは、通常、同等の速度を提供し、はるかに複雑です。また、標準のマージソートとは異なり、インプレースマージソート安定ソートではありません。それよりもリンクされたリストの場合、アルゴリズムは、より多くのスペースを使用しない、既にリスト表現で使用されるが、Oは（（のK の）ログ）再帰トレースに使用。いくつかは、あなたが与えられたデータ構造にソートされていても、データ構造は、本質的にO（のN の）余分なあなたが操作しているデータ（例えば、リンクを持っているので、リンクされたリストをソートする場所ではないことを主張するだろう）リストでます。

他のヒント

どうやら、それはあります。 インプレースマージソートを説明するこのホワイトペーパー：

  

2つは、インプレース古典マージソートアルゴリズムの変異体は、詳細に分析されています。最もNログ2 N + O（N）の比較及び3Nログ2 N + O（N）に移動まず、単純変異行うソートN要素に。第二は、より高度な変異体は、最もNログ2 N + O（N）の比較に必要と「Nは、任意の固定のために、2 Nに移動するログ」？ 0と任意のN？ N（ "）。理論的には、二番目はヒープソートの高度なバージョンに比べて優れている。実際には、インデックス操作でオーバーヘッドのために、私たちの最速のインプレースマージソートの振る舞いはまだ50パーセント程度遅くボトムアップヒープソートより。しかし、我々の実装では、インプレースマージに基づいてマージソートアルゴリズムに比べて実用的である。

ユルキKatajainen、トミパサネン、ユッカTeuhola、 "実用的なインプレースマージソート"（1996）。

ここでのJava実装である

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}
public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

ここで、ユニットテストは

private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}

いいえ、あなたはいつもにソートされた要素をマージするために余分なデータ構造が必要になります。そうでない場合、あなたはちょうどあなたがすでにソートされたものを上書きすることがあります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top