快速排序比較計數

Question

我想使用這些快速排序方法來弄清楚有多少比較正在發生。我們給出了一個全局變量，它可以進行計數，但是我們不能在使用全局變量時使用全局變量。相反，我們需要遞歸計算比較結果。現在我正試圖弄清楚如何做到這一點，而我並不是在尋找答案，我正試圖在如何解決這個問題上採取正確的步驟。我一直在嘗試幾個小時的事情，但沒有運氣。

static int qSortCompares = 0; // GLOBAL var declaration 

/** 
* The swap method swaps the contents of two elements in an int array. 
* 
* @param The array containing the two elements. 
* @param a The subscript of the first element. 
* @param b The subscript of the second element. 
*/ 
private static void swap(int[] array, int a, int b) { 
    int temp; 

    temp = array[a]; 
    array[a] = array[b]; 
    array[b] = temp; 
} 

public static void quickSort(int array[]) { 
    qSortCompares = 0; 
    int qSCount = 0; 
    doQuickSort(array, 0, array.length - 1); 

} 

/** 
* The doQuickSort method uses the QuickSort algorithm to sort an int array. 
* 
* @param array The array to sort. 
* @param start The starting subscript of the list to sort 
* @param end The ending subscript of the list to sort 
*/ 
private static int doQuickSort(int array[], int start, int end) { 
    int pivotPoint; 
    int qSTotal = 0; 
    if (start < end) { 

     // Get the pivot point. 
     pivotPoint = partition(array, start, end); 

     // Note - only one +/= 
     // Sort the first sub list. 
     doQuickSort(array, start, pivotPoint - 1); 

     // Sort the second sub list. 
     doQuickSort(array, pivotPoint + 1, end); 

    } 

    return qSTotal; 
} 

/** 
* The partition method selects a pivot value in an array and arranges the 
* array into two sub lists. All the values less than the pivot will be 
* stored in the left sub list and all the values greater than or equal to 
* the pivot will be stored in the right sub list. 
* 
* @param array The array to partition. 
* @param start The starting subscript of the area to partition. 
* @param end The ending subscript of the area to partition. 
* @return The subscript of the pivot value. 
*/ 
private static int partition(int array[], int start, int end) { 
    int pivotValue; // To hold the pivot value 
    int endOfLeftList; // Last element in the left sub list. 
    int mid;   // To hold the mid-point subscript 
    int qSCount = 0; 

    // see http://www.cs.cmu.edu/~fp/courses/15122-s11/lectures/08-qsort.pdf 
    // for discussion of middle point - This improves the almost sorted cases 
    // of using quicksort 
    // Find the subscript of the middle element. 
    // This will be our pivot value. 
    mid = (start + end)/2; 

    // Swap the middle element with the first element. 
    // This moves the pivot value to the start of 
    // the list. 
    swap(array, start, mid); 

    // Save the pivot value for comparisons. 
    pivotValue = array[start]; 

    // For now, the end of the left sub list is 
    // the first element. 
    endOfLeftList = start; 

    // Scan the entire list and move any values that 
    // are less than the pivot value to the left 
    // sub list. 
    for (int scan = start + 1; scan <= end; scan++) { 
     qSortCompares++; 
     qSCount++; 
     if (array[scan] < pivotValue) { 
      endOfLeftList++; 
      // System.out.println("Pivot=" + pivotValue + "=" + endOfLeftList + ":" + scan); 
      swap(array, endOfLeftList, scan); 
     } 
    } 

    // Move the pivot value to end of the 
    // left sub list. 
    swap(array, start, endOfLeftList); 

    // Return the subscript of the pivot value. 
    return endOfLeftList; 
} 

/** 
* Print an array to the Console 
* 
* @param A 
*/ 
public static void printArray(int[] A) { 
    for (int i = 0; i < A.length; i++) { 
     System.out.printf("%5d ", A[i]); 
    } 
    System.out.println(); 
} 

/** 
* @param args the command line arguments 
*/ 
public static void main(String[] args) { 
    final int SIZE = 10; 
    int[] A = new int[SIZE]; 

    // Create random array with elements in the range of 0 to SIZE - 1; 
    System.out.printf("Lab#2 Sorting Algorithm Performance Analysis\n\n"); 

    for (int i = 0; i < SIZE; i++) { 
     A[i] = (int) (Math.random() * SIZE); 
    } 

    System.out.printf("Unsorted Data = %s\n", Arrays.toString(A)); 

    int[] B; 

    // Measure comparisons and time each of the 4 sorts 
    B = Arrays.copyOf(A, A.length); // Need to do this before each sort 
    long startTime = System.nanoTime(); 
    quickSort(B); 
    long timeRequired = (System.nanoTime() - startTime)/1000; 

    System.out.printf("Sorted Data = %s\n", Arrays.toString(B)); 
    System.out.printf("Number of compares for quicksort  = %8d time = %8d us Ratio = %6.1f compares/us\n", qSortCompares, timeRequired, qSortCompares/(double) timeRequired); 

    // Add code for the other sorts here ... 
} 

指令給出了一些線索，但我還是輸了：

快速排序的方法目前使用全局變量計算比較的＃。這不是一個好的編程技術。修改quicksort方法以通過傳遞參數來計數比較。這是比較棘手的，因爲比較是在分區方法中完成的。您應該能夠看到在調用分區方法之前可以確定比較次數。您將需要從Quicksort方法中返回此值，並修改quickSort頭以將此值傳遞給每個遞歸調用。您需要遞歸添加計數。

作爲遞歸計數的替代方案，您可以保持代碼原樣並在未經修改的情況下完成實驗。

我一直在看這個任務的方式，我在名爲qSCount的分區方法中做了一個變量，當它被調用時將統計進行了多少次比較。但是我不能使用這個變量，因爲我沒有返回它。我不知道我將如何在該狀態下使用遞歸。我的想法是在每次qSCount有一個值後，我可以以某種方式將它存儲在qQuotal下的doQuickSort方法中。但是再次提示說我需要在quicksort中創建一個參數，所以我感到很困惑。

Answer 1

爲了用遞歸方法（沒有全局變量）來計算某些東西，我們需要返回它。您有：

private static int doQuickSort(int array[], int start, int end)

這是正確的想法。但由於比較實際中

private static int partition(int array[], int start, int end)

你需要有分區返回很多比較是如何製作的發生。

這給我們留下了兩個選項：

1. 我們可以創建或使用現有的Pair類有這個方法返回一個對整數，而不是僅僅一個（樞軸）的。
2. 我們可以創建一個計數器類並傳遞一個計數器對象，並在那裏進行計數。這消除了返回另一個值的需要，因爲該參數可用於增加計數。