シェルの並べ替えでの比較の回数を数える

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の部分では、2つのオブジェクトを比較するために一般的に使用される方法でさえあります。したがって、less関数がsortメソッド内で直接呼び出された場合にのみカウントする必要があります。その他の場合はisSortedとisHsortedはアサーションがあるためです。

アサーションは、プログラムに関する前提条件をテストできるようにするJavaプログラミング言語の文です。

これはあなたのエクササイズなので、簡単に解答することは避けてください。詳細なコード解を書くことはできません。私はあなたに別の提案を与えることができます

しかし、あなたはsortメソッドにlessの代わりに呼び出される新しいメソッドlessWithCounterを作成しようとすることができます。