Подсчет операций с массивами в сортировке Shell, используемой для целочисленных массивов

Question

Я пытаюсь подсчитать количество операций с массивами (присвоений в / из массива и сравнений с элементами массива), которые происходят во всем методе сортировки Shell, который принимает массив Integer.

Этокод, который использует моя сортировка Shell

 public static <T extends Comparable<? super T>> void shellSort(T[] a) {
    int gap = a.length / 2;
    while (gap >= 1) {
        if (gap % 2 == 0) {
            ++gap;
        }
        for (int i = gap; i < a.length; ++i) {
            int p = i;
            numAsgn++;
            T temp = a[p];
            numComp++;
            while (p >= gap && a[p - gap].compareTo(temp) > 0) {
                numAsgn++;
                a[p] = a[p - gap];
                p -= gap;
            }
            numAsgn++;
            a[p] = temp;
        }
        if (tracing) {
            System.out.println("...gap=" + gap + ": " + Arrays.toString(a));
        }
        gap /= 2;
    }
}

Это ожидаемый вывод.

(Примечание: я выполняю то же самое для других методов сортировки, но это не имеет отношения к моему вопросу)

Вывод, который я получаю для своего вида оболочки:

Итак, из этого я пришел к выводу, что мне не хватает где-то обновить значение numComp, но я не могу понять, где это находится в моем коде.Любая помощь приветствуется.

Кроме того, я попытался изменить счет таким образом.но безрезультатно.

//numComp++;
            while (p >= gap && a[p - gap].compareTo(temp) > 0) {
                numComp++;
                numAsgn++;
                a[p] = a[p - gap];
                p -= gap;
            }

Я не понимаю, как это возможно, поскольку цикл будет обновлять numComp++ более одного раза, но здесь число существенно ниже.

Answer 1

Попробуйте:

.....
T temp = a[p];
numComp++;
boolean in = false;
while (p >= gap && a[p - gap].compareTo(temp) > 0) {
    if(in) numComp++;
    in = true;
    numAsgn++;
    a[p] = a[p - gap];
    p -= gap;
}
.....

ключ не для подсчета дважды вне сравнения.

А затем часть:

if (gap % 2 == 0) {
    ++gap;
}

здесь это кажется неправильным и необязательным, просто удалите его.

Полный код:

public static <T extends Comparable<? super T>> void shellSort(T[] a) {
    int gap = a.length / 2;
    int numAsgn = 0, numComp = 0;
    while (gap >= 1) {
        for (int i = gap; i < a.length; ++i) {
            int p = i;
            numAsgn++;
            T temp = a[p];
            numComp++;
            boolean in = false;
            while (p >= gap && a[p - gap].compareTo(temp) > 0) {
                if (in)
                    numComp++;
                in = true;
                numAsgn++;
                a[p] = a[p - gap];
                p -= gap;
            }
            numAsgn++;
            a[p] = temp;
        }
        gap /= 2;
    }
    System.out.println(numComp + "," + numAsgn);
}

Answer 2

        numComp++; // comparing perhaps more than once but only counted as once here
        while (p >= gap && a[p - gap].compareTo(temp) > 0) { // this loop will result in multiple comparisons, is it not?
            numAsgn++;
            a[p] = a[p - gap];
            p -= gap;
        }

Поскольку требуется прямое решение, как насчет того, чтобы записать внутренние сравнения отдельно и затем добавить их к счетчику сравнения total следующим образом:

        numComp++; // for the loop termination comparison;
        int innerComp = 0; // for the loop non-termination comparison;
        while (p >= gap && a[p - gap].compareTo(temp) > 0) {
            innerComp++;
            numAsgn++;
            a[p] = a[p - gap];
            p -= gap;
        }
        numComp += innerComp;