Java MergeSort：比較とスワップカウンタ

Question

私は次のMergeSortクラスを持っています。私は比較とスワップのカウンターを実装する必要があります。私の比較とスワップカウンターが正しい場所にあるかどうか確認してもらえますか？

ご覧のとおり、スワップカウンタと比較カウンタの2つのクラスプロパティがあります。私が正確にポジティブではないところは、A）swapCountとcompareCount（runSortメソッドまたはmergeSortメソッドで）を初期化し、B）マージメソッドのswapCount ++をどこに配置するかです。私は確かにcompareCount ++が正しい場所にあると確信しています。

ここにコードがあります。返信したすべての人に事前に感謝！

public class MyMergeSort { 

    private int swapCount; 
    private int compareCount; 

    public void runSort() { 
     //this.compareCount = 0; 
     //this.swapCount = 0; 

     mergeSort(this.sortItems,0,sortItems.length); 
    } 

    public void mergeSort(String[] data, int first, int n) { 

     int n1; // Size of the first half of the array 
     int n2; // Size of the second half of the array 
     this.compareCount = 0; 
     this.swapCount = 0; 

     if (n > 1) { 
      // Compute sizes of the two halves 
      n1 = n/2; 
      n2 = n - n1; 

      mergeSort(data, first, n1);  // Sort data[first] through data[first+n1-1] 
      mergeSort(data, first + n1, n2); // Sort data[first+n1] to the end 

      // Merge the two sorted halves. 
      merge(data, first, n1, n2); 
     } 

    } 

    private void merge(String[] data, int first, int n1, int n2) { 

     String[] temp = new String[n1+n2]; // Allocate the temporary array 
     int copied = 0; // Number of elements copied from data to temp 
     int copied1 = 0; // Number copied from the first half of data 
     int copied2 = 0; // Number copied from the second half of data 
     int i;   // Array index to copy from temp back into data 

     // Merge elements, copying from two halves of data to the temporary array. 
     while ((copied1 < n1) && (copied2 < n2)) { 

      compareCount++; 

      if (data[first + copied1].compareTo(data[first + n1 + copied2]) < 0) { 
       temp[copied++] = data[first + (copied1++)]; 

       //swapCount++; 

      } 
      else { 
       temp[copied++] = data[first + n1 + (copied2++)]; 

       swapCount++; 
      } 
     } 

     // Copy any remaining entries in the left and right subarrays. 
     while (copied1 < n1) 
      temp[copied++] = data[first + (copied1++)]; 
     while (copied2 < n2) 
      temp[copied++] = data[first + n1 + (copied2++)]; 

     // Copy from temp back to the data array. 
     for (i = 0; i < n1+n2; i++) 
      data[first + i] = temp[i]; 
    } 

} 

**更新2011/11/28 **良いニュース。私は最終的に私が探していただけのものを見つけたと思う：

http://www.cs.carleton.edu/faculty/adalal/teaching/f04/117/notes/nov08/Sort.java

そのコードの作者に大きな感謝を！

Answer 1

適切なカウントを実行するには、カウントしているものが発生するたびにカウント値をインクリメントする必要があります。たとえば：

は

if (n > 2) { 
    a = b; 
    swapCount++; 
} 
compareCount++; // because the condition of the if statement 

これは、あなたがswapCountとcompareCountがアクセス可能であるようにあなたの方法を構築し、短絡が実際のカウントから発散しないように、あなたのロジックを修正する必要があるかもしれませんを意味します。たとえば、

if ((a > 5) && (b > 5)) { 
    ... 
} 

を書いて、あなたは比較1が行われ、または2されたかどうかを確認するために、ロジックを追加する必要があると思いますので、compareCountを更新する簡単な方法を得ることができませんでした。これを行うには、あなたは単ににより悪い読み込む異なる方法

if (a > 5) { 
    if (b > 5) { 
    } 
    compareCount++; 
} 
compareCount++; 

であなたの化合物の比較を書くためにはるかに良いだろう、少なくとも追加の代わりに

if (a > 5) { 
    compareCount++; 
} else { 
    compareCount += 2; 
} 

を比較追加したいです」 if文 "はインクリメントする条件を決定する際にはより巧妙です。compareCount。