Java MergeSort: Vergleichen und tauschen Zähler

Question

Ich habe die folgende MergeSort-Klasse und ich muss vergleichen und tauschen Zähler. Kann jemand bitte bestätigen, wenn meine Vergleichs- und Tauschenzähler an den richtigen Positionen sind?

Wie Sie sehen werden, habe ich zwei Klasseneigenschaften für die Swap- und Vergleichszähler. Wo ich nicht genau positiv bin, wo A) Ich initialisiere die swapCount und compareCount (in runSort-Methode oder mergeSort-Methode?) Und B) wo genau swapCount ++ in der Merge-Methode platziert werden sollte. Ich bin mir ziemlich sicher, dass compareCount ++ an der richtigen Stelle ist.

Hier ist der Code. Vielen Dank im Voraus an alle, die antworten!

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]; 
    } 

} 

** Update ** 2017.11.28 gute Nachricht. Ich glaube, ich fand schließlich genau das, was ich suchte:

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

Vielen Dank an den Autor des Codes!

Answer 1

Um das korrekte Zählen zu implementieren, müssen Sie den Zählwert jedesmal erhöhen, wenn das Ding, das Sie zählen, auftritt. Zum Beispiel:

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

Dies bedeutet, dass Sie benötigen, um Ihre Methoden zu strukturieren, so dass swapCount und compareCount zugänglich sind, und überarbeiten Sie Ihre Logik, so dass ein Kurzschluss nicht von der tatsächlichen Zählung abweichen wird. Zum Beispiel könnten Sie nicht

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

schreiben und eine einfache Möglichkeit der Aktualisierung der compareCount erhalten, weil Sie in der Logik hinzufügen müssen, Sie zu sehen, wenn man erfolgte vergleichen, oder zwei. Um das zu tun, würde man zumindest eine zusätzliche vergleichen

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

Stattdessen wäre es viel besser sein, einfach Ihre Verbindung Vergleich in einer anderen Art und Weise schreiben

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

, die mehr schlecht liest im " if-Anweisung "aber ist sauberer bei der Bestimmung der Bedingungen für die Erhöhung compareCount.