Java MergeSort : 카운터 비교 및 ​​교환

Question

다음 MergeSort 클래스가 있으므로 비교 및 ​​스왑 카운터를 구현해야합니다. 내 비교 및 ​​교환 카운터가 올바른 위치에 있는지 누군가 확인해 주시겠습니까?

위와 같이 스왑 및 카운터 비교를위한 두 가지 클래스 속성이 있습니다. 정확히 어디에 긍정적이지 않은가? 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]; 
    } 

} 

** 업데이트 11/28/2017 ** 좋은 소식. 나는 마침내 내가 찾던 그냥 뭐 찾은 것 같아요 :

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)) { 
    ... 
} 

를 작성하고 당신이 한 짓을, 또는이 된 비교 있는지 확인하기 위해 로직을 추가해야 할 것 때문에 compareCount를 업데이트하는 쉬운 방법을 가져올 수 없습니다. 그렇게하려면, 당신은 단순히 더 제대로 읽는 다른 방법

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

에서 화합물의 비교를 작성하는 더 나은 것 이상의 추가 대신

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

비교 추가하려는 " if 문 "을 사용하지만 증가하는 조건을 결정할 때 더 깨끗합니다. compareCount.