快速排序比较计数

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. 我们可以创建一个计数器类并传递一个计数器对象，并在那里进行计数。这消除了返回另一个值的需要，因为该参数可用于增加计数。