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

Question

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

public int[] quickSort(int[] array, int start, int end){


    if (start < end){
        counter++;//1st comparison here
        int pivot;  

        pivot = Partition(array, start, end);
        quickSort(array, start, pivot - 1);
        quickSort(array, pivot + 1, end );
    }
return  array;
}

private int Partition(int[] array, int start, int end) {
    int pivot = array[end];
    int i = start - 1;

    for(int j = start; j <= end - 1; j++){

        counter++;//2nd comparison here


        if (array[j] <= pivot){
            counter++;//3rd comparison here
            i = i + 1;

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

    }

    int temp = array[i+1];
    array[i+1] = array[end];
    array[end] = temp;

    return i + 1;
}

Answer 1

Для теории подсчитываются только сравнения элементов массива, а не сравнения индексов с границами, поэтому вы должны оставить только второе counter++; (вам нужно увеличивать счетчик независимо от результата сравнения).

Тогда возникает вопрос, с какими теоретическими значениями вы сравниваете.Существуют разные реализации быстрой сортировки, которые используют несколько различное число сравнений.В частности, ваш выбор оси не делает попытки избежать экстремальных значений, поэтому эта реализация легко опустится до поведения O (n ^ 2).