Быстрый подсчет сравнения

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 имел значение, я мог каким-то образом сохранить его в методе doQuickSort в qSTotal. Но опять же намек на то, что мне нужно сделать параметр в 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. Мы можем создать класс счетчика и передать объект-счетчик и провести подсчет. Это устраняет необходимость возврата другого значения, поскольку параметр может использоваться для увеличения количества.