0

ランダムなサイズ (100,000 要素以上) の大規模なデータ セットを並べ替えるためのマージソート アルゴリズムをインプレースで作成しました。データがほとんどソートされているときに挿入ソートを入れて、アルゴリズムを少し速く実行することを考えていました。これが適切なマージソートで可能かどうか疑問に思っていましたか?

これが私のコードの一部です。

public static void merge(ArrayList<String> list, int low, int high) {
   if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

public static void mergeSort(ArrayList<String> list, int first, int mid,
        int last) {
    int left = first;
    int right = mid + 1;
    String holder = "";

    // if mid <= mid+1 skip merge
    if (compareTo(list.get(mid), list.get(right)) <= 0) {
        return;
    }

    while (left <= mid && right <= last) {
        // if left index <= right index then just add to left
        if (compareTo(list.get(left), list.get(right)) <= 0) {
            left++;
        } else {
            holder = list.get(right);
            copyList(list, left, right - left);//moves everything from left to right-left                       up one index in the arraylist
            list.set(left, holder);

            left++;
            mid++;
            right++;
        }
    }
    // what is left is in place

}

public static void copyList(ArrayList<String> source, int srcPos, int length) {
    String temp1 = "";
    String temp2 = source.get(srcPos);
    for (int i = 0; i < length; i++) {
        temp1 = source.get(srcPos + 1);
        source.set(srcPos + 1, temp2);
        temp2 = temp1;
        srcPos++;
    }
}

今、最初に配列リストに要素をスローするときに要素の数をカウンターで挿入ソートを実装し、次にマージメソッドを次のように変更することを考えていました。

public static void merge(ArrayList<String> list, int low, int high) {
   if(high-low==dataSize-1){
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        insertionSort(list);
   }else if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

ただし、これにより、実際には私のアルゴリズムは永遠にかかります。データは完全にランダムに生成され、ほとんどソートされていないため、アルゴリズムは n^2 を実行していると思います。

私は何を間違っていますか？助言がありますか？私の推測では、マージソートが適切に行われているため、機能しません。

ありがとう！

4

1 に答える 1

0

このようなアルゴリズムは複雑で、間違えやすいです。私は非常によく似たものを実装しました:インプレース安定マージ sort。また、小さなサブリストには挿入ソートを使用します。ソースコードを見て、あなたがしていることと比較することをお勧めします。インプレースの安定したクイックソートにも興味があるかもしれません。

私が間違っていない限り、実装は安定していません (等しい要素を再配置する可能性があります)。ユースケースによっては、これが問題になる場合とそうでない場合があります。

また、 copyList メソッドは O(n) であり、 n 回呼び出されるため、実装は O(n^2) のようです。

insertSort について: とは何dataSizeですか? なぜ equals を使用して比較するのですか? <代わりに使いませんか？その場合、else if (low < high)は冗長です (常に true です)。

于 2012-10-25T07:15:02.860 に答える