印刷変数が正常に動作しません - Java

Question

クイックソートアルゴリズムで比較とスワップの回数を数えたいと思います。 これは私のコードです：

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high , int comparisons ,int swaps){ 

    ArrayList<Integer> sortedData = new ArrayList<Integer>(); 

    if(low< high) { 
     int pivotIndex = low; // Assume first element is the pivot 
     int pivot = data.get(low);// The pivot value 
     data.set(pivotIndex, data.get(high));// Swap pivot with last item 

     data.set(high, pivot); 
     int i = low - 1; 
     int j = high; 


     do {     
      do {i++;} while (data.get(i)< pivot); 
      do {j--;} while (j>=0 && data.get(j)> pivot); 
      comparisons ++ ; 
      if (i < j) { 
       int temp = data.get(i); 
       data.set(i, data.get(j)); 
       swaps ++ ; 
       data.set(j, temp); 
       swaps ++ ; 
      } 
     } while (i < j); 

     data.set(high, data.get(i)); // Put the pivot back in the middle 
     swaps ++ ; 
     data.set(i, pivot); 
     swaps ++ ; 

     quickSort(data, low, i - 1 , comparisons , swaps);// Recursive sort left list 
     quickSort(data, i + 1 ,high ,comparisons , swaps);// Recursive sort right list 
    } 

    System.out.println("Quick S swaps : " + swaps); 
    System.out.println("Quick S comparisons : " + comparisons); 

    sortedData = data; 

    return sortedData ; 
} 

私はループや再帰関数の後にprint文を入れますが、出力は各ループとのスワップとの比較です！ 特定の地点まで増加してから、その地点に戻るために減少します！

Quick S swaps : 2 
Quick S comparisons : 1 
Quick S swaps : 4 
Quick S comparisons : 2 
Quick S swaps : 6 
Quick S comparisons : 3 
Quick S swaps : 8 
Quick S comparisons : 4 
Quick S swaps : 10 
Quick S comparisons : 5 
.. 
.. 
.. 
.. 
.. 
Quick S swaps : 2986 
Quick S comparisons : 1493 
Quick S swaps : 2988 
Quick S comparisons : 1494 
Quick S swaps : 2990 
Quick S comparisons : 1495 
Quick S swaps : 2992 
Quick S comparisons : 1496 
Quick S swaps : 2994 
Quick S comparisons : 1497 
Quick S swaps : 2998 
Quick S comparisons : 1499 
Quick S swaps : 2998 
Quick S comparisons : 1499 
Quick S swaps : 2998 
Quick S comparisons : 1499 
Quick S swaps : 2994 
Quick S comparisons : 1497 
Quick S swaps : 2992 
Quick S comparisons : 1496 
Quick S swaps : 2990 
Quick S comparisons : 1495 
Quick S swaps : 2988 
Quick S comparisons : 1494 
Quick S swaps : 2986 
Quick S comparisons : 1493 
.. 
.. 
.. 
.. 
.. 
Quick S swaps : 12 
Quick S comparisons : 6 
Quick S swaps : 10 
Quick S comparisons : 5 
Quick S swaps : 8 
Quick S comparisons : 4 
Quick S swaps : 6 
Quick S comparisons : 3 
Quick S swaps : 4 
Quick S comparisons : 2 
Quick S swaps : 2 
Quick S comparisons : 1 

なぜこれが起こりますか？どうすれば修正できますか？

Answer 1

int comparisonsとint swapsと呼び出しスタックに配置されたローカル変数。 quickSort(ArrayList<Integer> data , int low , int high , int comparisons ,int swaps)への各呼び出しには、これらの変数の独自のコピーがあります。

再帰呼び出しを行うたびに、これらの変数の高い値を次の呼び出しに渡しますが、再帰呼び出しが戻ると、これらの変数の以前のコピーの値が低くなります。

変数が1つで、変数がswapsである場合は、quickSortメソッドを含むクラスの静的変数またはインスタンス変数を作成し、メソッドのシグネチャから削除することができます。

変数が複数回印刷されている場合は、再帰的メソッドの外にprintlnステートメントを移動する必要があります。そのメソッドは複数回呼び出され、これらの変数を印刷するたびに呼び出されるためです。例えば

：別の方法として

... 

private int comparisons = 0; 
private int swaps = 0; 

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high) 
{ 
    ... 
} 

public printCounters() 
{ 
    System.out.println("Quick S swaps : " + swaps); 
    System.out.println("Quick S comparisons : " + comparisons); 
} 

.... 

someObj.quickSort(data, 0, data.size() - 1); // sort the list 
someObj.printCounters(); // print the counters 

、JB Nizetはコメントとして、あなたには、いくつかの変更可能なカウンタを渡すことができます。例えば

、int配列：

someObj.quickSort(data, 0, data.size() - 1, new int[]{0}, new int[]{0}); 

と

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high , int[] comparisons ,int[] swaps) 
{ 
    // here you change each comparisons++ to comparisons[0]++ 
    // and each swaps++ to swaps[0]++ 
    // you also print comparisons[0] and swaps[0] 
}