Как подсчитать сравнения и свопы в quicksort?

Question

public class IntQuickSorter 
{ 
    public static int numOfComps = 0, 
        numOfSwaps = 0; 

    public static void main(String[] args) 
    { 
     // Create an int array with test values. 
     int[] values = { 1, 2, 3, 4, 5, 6 }; 
     //int[] values = { 5, 1, 3, 6, 4, 2 }; 
     //int[] values = { 5, 7, 2, 8, 9, 1 }; 

     System.out.println("\n\nQuick Sort:"); 

     // Display the array's contents. 
     System.out.println("\nOriginal order: "); 
     for (int element : values) 
     System.out.print(element + " "); 

     // Sort the array. 
     quickSort(values); 

     //System.out.println("\n\nNumber of comps = " + numOfComps); 
     //System.out.println("Number of swaps = " + numOfSwaps); 

     // Display the array's contents. 
     System.out.println("\nSorted order: "); 
     for (int element : values) 
     System.out.print(element + " "); 

     System.out.println(); 
    } 

    public static void quickSort(int array[]) 
    { 
     doQuickSort(array, 0, array.length - 1); 
     System.out.println("\n\nNumber of comps = " + numOfComps); 
     System.out.println("Number of swaps = " + numOfSwaps); 
    } 

    private static void doQuickSort(int array[], int start, int end) 
    { 
     int pivotPoint; 

     if (start < end) 
     { 
     numOfComps++; 

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

     // Sort the first sub list. 
     doQuickSort(array, start, pivotPoint - 1); 

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

    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 

     // 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++) 
     { 

     if (array[scan] < pivotValue) 
     { 
      endOfLeftList++; 
      swap(array, endOfLeftList, scan); 

       numOfSwaps ++; 
     } 
     numOfComps++; 
     } 

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

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

    private static void swap(int[] array, int a, int b) 
    { 
     int temp; 

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

Как закодировать эту программу быстрой сортировки в Java, чтобы подсчитать количество сравнений и количество свопов? Теперь, когда у меня есть своп-код, он подсчитывает свопы даже с отсортированным массивом чисел, и это не должно. И код сравнения в нужном месте? Спасибо за любую помощь.

Answer 1

Если у меня есть своп-код, он учитывает свопы даже с отсортированным массивом чисел, и это не должно.

Это не совсем точная информация. В отсортированном массиве будет есть свопы с быстрой сортировкой, вот как работает поворот и разбиение. Вот анимация типичной быстрой сортировки с использованием отсортированного списка. Animationgist

Кроме того, удалить это сравнение:

if (start < end) 
     { 
     numOfComps++; 

Потому что это не является "ключом сравнение" двух вещей в массиве, только из ваших показателей.
Помимо этого, ваши сравнения и свопы выглядят в нужном месте.

Answer 2

Вы можете использовать следующий метод http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-
Насколько я помню, он использует быструю сортировку Алгоритма Построения
При реализации у вас есть компаратор, то вы можете увеличивать счетчик при компараторе вызова (число сравнений) и увеличиваете другой счетчик, когда один значение больше, чем другое (тогда происходит обмен).