이 코드를 사용하여 쉘 정렬의 비교 횟수를 계산하면

Question

, 나는 요소 비교 수를 계산해야합니다. 즉, 비교가 sort() 메서드의 for 루프 또는 less() 메서드 내에서 수행되는지 확신 할 수 없습니다. 도와 주셔서 정말 감사합니다.

public class Shell { 
private static int compares; 
// This class should not be instantiated. 
private Shell() { } 

/** 
* Rearranges the array in ascending order, using the natural order. 
* @param a the array to be sorted 
*/ 
public static void sort(Comparable[] a) { 
    int n = a.length; 

    // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1; 
    while (h < n/3) h = 3*h + 1; 

    while (h >= 1) { 
     // h-sort the array 
     for (int i = h; i < n; i++) { 
      for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) { 
       exch(a, j, j-h); 
      } 
     } 
     assert isHsorted(a, h); 
     h /= 3; 
    } 
    assert isSorted(a); 
} 

/****************************************** ********************************* * 도우미 정렬 기능. ************************************************ **************************/

// is v < w ? 
    private static boolean less(Comparable v, Comparable w) { 
    return v.compareTo(w) < 0; 
    } 

// exchange a[i] and a[j] 
private static void exch(Object[] a, int i, int j) { 
    Object swap = a[i]; 
    a[i] = a[j]; 
    a[j] = swap; 
} 

/*************** *************************************************** ********** * 배열이 정렬되어 있는지 확인하십시오 - 디버깅에 유용합니다. ************************************************ *************************/아마 당신이 묻는, 코드가 고전적인 학생 운동과 같은 것을

private static boolean isSorted(Comparable[] a) { 
     for (int i = 1; i < a.length; i++) 
     if (less(a[i], a[i-1])) return false; 
     return true; 
} 

// is the array h-sorted? 
private static boolean isHsorted(Comparable[] a, int h) { 
    for (int i = h; i < a.length; i++) 
     if (less(a[i], a[i-h])){ 
      return false; 
     } 
    return true; 

} 

// print array to standard output 
     private static void show(Comparable[] a) { 
     for (int i = 0; i < a.length; i++) { 
      StdOut.println(a[i]); 
    } 
} 

/** 
* Reads in a sequence of strings from standard input; Shellsorts them; 
* and prints them to standard output in ascending order. 
* 
* @param args the command-line arguments 
*/ 
public static void main(String[] args) { 
    String[] a = StdIn.readAllStrings(); 
    Shell.sort(a); 
    show(a); 
} 

} 

Answer 1

을 감안할 때 sort 함수 내에서 호출 될 때 less 함수에 의해 수행 된 요소 비교의 수만 계산하십시오. 내가 틀렸다면 질문을 업데이트하여 타겟에 대한 더 자세한 설명을 추가하십시오.

위에서 볼 수 있듯이 less 함수가 호출 될 때마다 비교가 이루어집니다. 그러나 코드 less 조각에서 두 개의 객체를 비교하는 데 일반적으로 사용되는 방법입니다. 따라서 less 함수가 sort 메서드 내에서 직접 호출 된 경우에만 계산해야합니다. 다른 경우 isSorted과 isHsorted은 어설 션이 있기 때문에 존재합니다.

어설 션은 Java 프로그램 언어의 문장으로, 프로그램에 대한 가정을 테스트 할 수 있습니다.

기억해보십시오.이 내용은 운동이기 때문에 쉬운 대답을 둘러 보지 말고 자세한 코드 솔루션을 작성하지 않아야합니다.

그러나 나는 또 다른 제안을 할 수 있습니다. less 대신 sort 메서드로 호출되는 lessWithCounter 메서드를 새로 만들려고 할 수 있습니다.