Оболочка сортировки: не работает с определенными комбинациями интервалов - PullRequest
Новая
       21

Оболочка сортировки: не работает с определенными комбинациями интервалов

0 голосов
/ 09 декабря 2011

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

Сортировка оболочки, как я ее написал, работает только иногда.Массив a - это массив из 100 целых чисел, не отсортированных, inc - это массив из 4 целых чисел, значениями которых являются интервалы, которые должна использовать сортировка оболочки (они уменьшаются, а окончательное значение всегда равно 1), count - это массивхранит счетчики для разных прогонов сортировки оболочки, cnt представляет значение счетчика, которое должно быть обновлено для этого прогона сортировки оболочки.

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

Кто-нибудь может помочь?Заранее спасибо! 

public static void shellSort(int[] a, int[] inc, int[] count, int cnt) {
    for (int k = 0; k < inc.length; k++) {
        for (int i = inc[k], j; i < a.length; i += inc[k]) {
            int tmp = a[i];
            count[cnt] += 1;
            for (j = i - inc[k]; j >= 0; j -= inc[k]) {
                if (a[j] <= tmp)
                    break;
                a[j + inc[k]] = a[j];
                count[cnt] += 1;
            }
            a[j + inc[k]] = tmp;
            count[cnt] += 1;
        }
    }
}

Ответы [ 2 ]

1 голос
/ 09 декабря 2011

Одна проблема состоит в том, что вы сортируете только одну последовательность inc[k] -шаг для каждого k, в то время как вы должны сортировать их все (вы только сортируете {a[0], a[s], a[2*s], ... , a[m*s]}, опуская {a[1], a[s+1], ... , a[m*s+1]} и т. Д.). Однако это должно влиять только на производительность (количество операций), а не на результат, поскольку последний проход является классической сортировкой вставки (inc[inc.length-1] == 1), поэтому следует сортировать массив независимо от того, что происходило раньше.

Я не вижу в коде ничего, что могло бы вызвать сбой. Может быть, массив inc не содержит того, что должен? Если вы выводите inc[k] в каждой итерации внешнего цикла, вы получите ожидаемый результат?

0 голосов
/ 09 декабря 2011

Ошибка в вашем i цикле управления: 

for (int i = inc[k], j; i < a.length; i += inc[k]) {

Должно быть: 

for (int i = inc[k], j; i < a.length; i++) {

Внутренний цикл j обрабатывает сравнение элементов, которые inc[k] отдельно.Внешний цикл i должен просто увеличиваться на 1, так же, как внешний цикл стандартной сортировки вставки.

Фактически, последний проход сортировки Shellsort с шагом 1 идентичен стандартной сортировке вставки.

...