2

Algorithms in Java 4th edition でマージソートを実装していました。私の基本的なマージ ソートは動作します。配列サイズが 7 未満の場合は、挿入ソートを使用してアルゴリズムを改善したいと考えています。これは明らかに効率的な改善だと思っていましたが、実際には、オリジナルの方が改善されたものよりも大きなデータに対して高速です。

これが私の改善されたマージソート、CUTOFF = 7 です:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

  // Copy to aux[]
  for (int i = lo; i <= hi; i++) {
    aux[i] = a[i];
  }

  // Merge back to a[]
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    if      (i > mid)              a[k] = aux[j++];
    else if (j > hi)               a[k] = aux[i++];
    else if (less(aux[i], aux[j])) a[k] = aux[i++];
    else                           a[k] = aux[j++];
  }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

  // #1 improvement
  // Stop condition for this recursion.
  // This time we add a CUTOFF, when the items in array
  // is less than 7, we will use insertion sort.
  if (hi <= lo + CUTOFF - 1) {
    Insertion.sort(a, lo, hi);
    return;
  }

  int mid = lo + (hi - lo) / 2;
  sort(a, aux, lo, mid);
  sort(a, aux, mid + 1, hi);
  if (!less(a[mid+1], a[mid])) return;
  merge(a, aux, lo, mid, hi);
}

public static void sort(Comparable[] a) {
  Comparable[] aux = new Comparable[a.length];
  sort(a, aux, 0, a.length - 1);
}

挿入ソートコード:

public static void sort(Comparable[] a, int lo, int hi) {
  for (int i = lo; i <= hi; i++) {
    for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
      exch(a, j, j - 1);
    }
  }
}

SortCompare.java を使用して実行時間を比較しました。

public class SortCompare {

  public static double time(String alg, Comparable[] a) {
    Stopwatch timer = new Stopwatch();
    if (alg.equals("Insertion")) Insertion.sort(a);
    if (alg.equals("Selection")) Selection.sort(a);
    if (alg.equals("Shell")) Shell.sort(a);
    if (alg.equals("Merge")) Merge.sort(a);
    if (alg.equals("MergeWithImprovements")) MergeWithImprovements.sort(a);
    //if (alg.equals("Quick")) Quick.sort(a);
    //if (alg.equals("Heap")) Heap.sort(a);
    if (alg.equals("InsertionWithSentinel")) InsertionWithSentinel.sort(a);
    return timer.elapsedTime();
  }

  public static double timeRandomInput(String alg, int N, int T) {
    // Use alg to sort T random arrays of length N.
    double total = 0.0;
    Double[] a = new Double[N];
    for (int t = 0; t < T; t++) {
      for (int i = 0; i < N; i++) {
        a[i] = StdRandom.uniform();
      }
      total += time(alg, a);
    }
    return total;
  }

  public static void main(String[] args) {
    String alg1 = args[0];
    String alg2 = args[1];
    int N = Integer.parseInt(args[2]);
    int T = Integer.parseInt(args[3]);
    double t1 = timeRandomInput(alg1, N, T);  // Total for alg1
    double t2 = timeRandomInput(alg2, N, T);
    StdOut.printf("For %d random Doubles\n   %s is", N, alg1);
    StdOut.printf(" %.1f times faster than %s\n", t2/t1, alg2);
  }
}

それぞれ 10000 個の要素を持つ 100 個の配列を生成しました。元のマージ ソートは、改善されたものよりも 30 倍高速です。

4

1 に答える 1

2

挿入ソート機能は間違いなく間違っています。j > 0終了条件に注意してください。を渡しますが、コードはまでずっと[lo..hi]反復できます。次のようなものが欲しいと思います：j1

public static void sort(Comparable[] a, int lo, int hi) {
  for (int i = lo + 1; i <= hi; i++) {
    for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
      exch(a, j, j - 1);
    }
  }
}
于 2013-08-06T02:20:12.990 に答える