Как подсчитать количество сравнений элементов в алгоритме быстрой сортировки?

Question

Когда дан массив элементов, как я могу подсчитать количество сравнений элементов, которые выполняет алгоритм?

Это не так просто, как просто добавить счетчик в метод разбиения.1005 * Вы не можете сделать это, потому что он считает только что выполненное сравнение, а не какое-либо из сравнений, выполненных, когда оно оценивается как ложное.j тоже), но я чувствую, что все еще что-то упускаю, если я делаю это таким образом.

Answer 1

Метод быстрой сортировки будет вызываться до тех пор, пока размер массива не станет равным 1, в этом случае наш массив будет отсортирован. В вашем коде, когда вы установили позицию, в которой будет меняться шарнир (в вашей части else if ) Вы не должны включать счетчик сравнения.

Вы можете использовать этот модифицированный метод разбиения

partition(A,p,r)
{

    pivot=A[r]; // Taking last element as pivot
    i=p;
    j=r;

    while (true)
    {

        while(A[i] < pivot && i <= r )
        {

            ++comparecounter;
            ++i;

        }

        while(A[j] >= pivot && j >= 0)
        {

            --j;
            ++comparecount;

        }

        if(i < j)
        {

            Exchange A[i] and A[j]

        }
        else
        {
            return j;
        }

В вышеприведенном алгоритме вы могли бы сделать countcompare глобальным, что повлекло бы за собой каждый вызов раздела. Это посчитало бы количество выполненных сравнений.

Answer 2

В идеале вы должны быть в состоянии сделать это путем анализа логики. Но если вы хотите, чтобы программа делала это для вас во время выполнения, то простой способ сделать это - иметь функцию для выполнения операции сравнения. Пусть функция увеличивает глобальную / статическую переменную при каждом ее вызове, а затем выполняет сравнение. В конце всей вашей логики просто напечатайте эту глобальную / статическую переменную.

    public class Myclass{

    public static int compareCount = 0;

    }

    /*
    * PASS parameter comparisonMethod as following
    * 0 for ==, 1 for >, 2 for >=, 3 for < and 4 for <==
    *  Method returns true or false by doing appropriate comparison based on comparisonMethod 
    */

    public bool compare(int i, int j, int comparisonMethod)
    {
      Myclass.compareCount++;
      if(comparisionMethod ==0) return i==j?true:false;
      if(comparisionMethod ==1) return i>j?true:false;
      if(comparisionMethod ==2) return i>=j?true:false;
      if(comparisionMethod ==3) return i<j?true:false;
      if(comparisionMethod ==4) return i<=j?true:false;   
    }


    private void partition(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = numbers[low + (high-low)/2];

        // Divide into two lists
        while (compare(i, j, 4)) {

            if (compare(array[i], pivot, 3)) {
                i++;
            }
            else if (compare(numbers[j], pivot, 2)) {
                j--;
            }

            else (compare(i, j, 4)) {
                exchange(i, j);
                i++;
                j--;
            }
        }
// At the end of the logic, Myclass.compareCount wil give number of comparisons made.

Answer 3

Вы можете встроить приращение сравнения внутри каждого оператора if ...

    if ((compareCount++ != -1) && (array[i] < pivot))
    ...
    else if ((compareCount++ != -1) && (numbers[j] > pivot))
    ...
    else if ((compareCount++ != -1) &&  (i <= j))

Он всегда оценивает первое предложение if, всегда возвращает true и всегда затем выполняет второе.