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

Question

Я пытаюсь сосчитать сравнения и обмены, которые требуются для сортировки Shell, чтобы отсортировать массив чисел int[] array = {1,2,3,4,5,6,7,8,9,10}.Со счетчиком сравнения, где он сейчас (comp), и счетчиком обмена, где он находится (exch), я получаю 22 сравнения и ноль обменов.Я считаю, что обмены с нулем верны, потому что это явно отсортированный массив, поэтому обмены не нужны.С массивом из 10 элементов я не думаю, что 22 сравнения будут правильными.Может кто-нибудь показать мне, где должны быть эти выражения, и объяснить, почему?Я был бы очень признателен.

public static void shellSort(int[] array) {
    int interval = array.length / 2;
    int comp = 0, exch = 0;
    while (interval != 0) {
        for (int i = 0; i < interval; i++) {
            for (int p = i + interval; p < array.length; p += interval) {
                int key = array[p];
                int j = p - interval;
                while (j >= 0) {
                    comp++;         //Comparison here
                    if (key < array[j]) {
                        array[j + interval] = array[j];
                    } else
                        break;
                    exch++;     //Exchange here
                    j -= interval;
                }
                array[j + interval] = key;
            }
        }
        interval /= 2;
    }
}

Answer 1

С теория :

{1,2,3,4,5,6,7,8,9,10}

1. с зазором 5 (10 >>> 1):

   {1,6}{2,7}{3,8}{4,9}{5,10}
     ^    ^    ^    ^    ^    --> 5 comparisons
   

2. с зазором 2 (5 >>> 1):

   {1,3,5,7,9}{2,4,6,8,10}
     ^ ^ ^ ^    ^ ^ ^ ^    --> 8 comparisons
   

3. с зазором 1 (2 >>> 1):

   {1,2,3,4,5,6,7,8,9,10}
     ^ ^ ^ ^ ^ ^ ^ ^ ^    --> 9 comparisons
   

Всего: 22 сравнения.Где проблема?:)

ОБНОВЛЕНИЕ

10,9,8,7,6,5,4,3,2,1

1. С зазором 5 (10 >>> 1):

   10,5  9,4  8,3  7,2  6,1
     ê    ê    ê    ê    ê  --> 5c, 5e
   

5,4,3,2,1,10,9,8,7,6

С зазором 2 (5 >>> 1):

5,3,1,9,7

5,3 
 ê        --> 1c, 1e --> 3,4,5,2,1,10,9,8,7,6
3,5,1                    ‾   ‾
 ê ê      --> 2c, 2e --> 1,4,3,2,5,10,9,8,7,6
1,3,5,9                  ‾   ‾   ‾
     ^    --> 1c
1,3,5,9,7
     ^ ê  --> 2c, 1e --> 1,4,3,2,5,10,7,8,9,6
                                      ‾   ‾   
4,2,10,8,6

4,2
 ê         --> 1c, 1e --> 1,2,3,4,5,10,7,8,9,6
2,4,10                      ‾   ‾
   ^       --> 1c
2,4,10,8
   ^  ê    --> 2c, 1e --> 1,2,3,4,5,8,7,10,9,6
2,4,8,10,6                          ‾   ‾‾
   ^ ê  ê  --> 3c, 2e --> 1,2,3,4,5,6,7,8,9,10
                                    ‾   ‾   ‾‾ 

С зазором 1 (2 >>> 1):

1,2,3,4,5,6,7,8,9,10
 ^ ^ ^ ^ ^ ^ ^ ^ ^   --> 9c

Я пришел к 27 сравнениям и 13 обменам.

Я почти уверен, что вы можете выполнить последний тест с ручкой и бумагой самостоятельно.:)