Подсчет сравнений и свопов в быстрой сортировке

Question

Я выполняю быструю сортировку по 2000 целым числам, считанным из файла и подсчитывающим сравнения и свопы, но я не уверен, что мои счетчики находятся в нужном месте, так как мои цифры кажутся неправильными, или что-то не так с сортировкой?

public int partition(int array[], int low, int high) 
    { 
        int pivot = array[low];

        while(low < high)
        {
            while(pivot < array[high] && low < high)
            {
                high = high - 1;
                compCounter++;
            }
            if(high != low)
            {
                array[low] = array[high];
                SwapCounter++;
                low++;
            }
            while(array[low] < pivot && low < high)
            {
                low = low +1;
                compCounter++;
            }
            if(high != low)
            {
                array[high] = array[low];
                SwapCounter++;
                high--;
            }
        }

        SwapCounter++;
        int temp = array[high];
        array[high] = pivot;
        return high;


    } 

    public void quickSort(int array[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pivotPoint = partition(array, low, high); 
            quickSort(array, low, pivotPoint-1); 
            quickSort(array, pivotPoint+1, high); 
        } 
    }  

Answer 1

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

    private static int CompCounter, SwapCounter;

    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 7 , 4, -1};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static int partition(int array[], int low, int high) {
        int pivot = array[high];

        int lowBound = low;
        for (int i = low; i < high; i++)
        {
            CompCounter++;
            if (array[i] < pivot) {
                int temp = array[lowBound];
                array[lowBound] = array[i];
                array[i] = temp;
                lowBound++;
                SwapCounter++;
            }
        }

        SwapCounter++;
        array[high] = array[lowBound];
        array[lowBound] = pivot;
        return lowBound;
    }

    public static void quickSort(int array[], int low, int high) {
        if (low < high)
        {
            int pivotPoint = partition(array, low, high);
            quickSort(array, low, pivotPoint - 1);
            quickSort(array, pivotPoint + 1, high);
        }
    }

Если хотите, вы можете использовать другой способ разделения для сортировки (другой алгоритм):

    public static int partitionSecondWay(int array[], int low, int high) {
    int pivot = array[low];
    int i = low - 1;
    int j = high + 1;
    while (true)
    {
        do
        {
            i++;
            CompCounter++;
        } while (array[i] < pivot);
        do
        {
            j--;
            CompCounter++;
        } while (array[j] > pivot);
        if (i >= j)
        {
            CompCounter++;
            return j; // notice if you use this way, then in quicksort you
            // must use quicksort(array, low, partition) and 
            // quicksort(array, partition + 1, high)
        }

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        SwapCounter++;
    }
}

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