Сравнение сортировки и обмен Shell - PullRequest
Новая
       26

Сравнение сортировки и обмен Shell

0 голосов
/ 27 марта 2019

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

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

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 && arr[j - gap] > temp; j -= gap) 
                    arr[j] = arr[j - gap]; 
                comparisons++;
                // put temp correct location 
                arr[j] = temp; 
                exchanges++;
            } 
        }
    }

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

...