Блог

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

Я пробовал считать их в других местах, но я полагаю, что они у меня в правильных местах. Единственная разница в значениях, которые я получаю, заключается в изменении разрыва, который, очевидно, изменил бы эффективность алгоритма, но это единственное, что меняет эффективность? Или мои значения неверны?

 int Sort(int arr[]) 
    { 
        int n = arr.length; 
        int exchanges = 0, comparisons = 0;

        // Start with a big gap, then reduce the gap 
        for (int gap = n/2; gap > 0; gap = gap*3   1) 
        { 
            //gapped insertion sort 
            for (int i = gap; i < n; i  = 1) 
            { 
                // add a[i] to the elements that have been gap 
                // sorted save a[i] in temp and make a hole at 
                // position i 
                exchanges  ;
                int temp = arr[i]; 

                // shift earlier gap-sorted elements up until 
                // location for a[i] is found 
                int j; 
                for (j = i; j >= gap amp;amp; arr[j - gap] > temp; j -= gap) 
                    arr[j] = arr[j - gap]; 
                comparisons  ;
                // put temp correct location 
                arr[j] = temp; 
                exchanges  ;
            } 
        }
    } 
  

Я ожидал получить другой результат для случайного набора значений. Я понимаю, что последовательность пробелов частично сортирует ее, но я получаю значения обменов (Swaps) — 10 и сравнений — 5
по возрастанию, убыванию и случайным значениям от 1 до 10. Что заставляет меня сомневаться в правильности моих значений. Делает ли сортировка оболочки ввод данных нечувствительным к сортировке при вставке? Приветствуется любая помощь / ввод.