Как я могу внедрить Shell Sort с бинарным поиском? - PullRequest
Новая
       98

Как я могу внедрить Shell Sort с бинарным поиском?

0 голосов
/ 02 мая 2020

Я только что обнаружил бинарную сортировку вставками, и сейчас я пытаюсь внедрить бинарный поиск в Shell Sort на Java (хотя я понимаю эту концепцию, у меня нет предыдущего опыта внедрения Shell Sort) .

Я думал, что должен был изменить только приращение, потому что оригинальное решение, которое я нашел (https://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html, адаптированный к Java для ArrayList), творило чудеса с шагом 1, но я я пробовал (как я тестирую с маленьким ArrayList), начиная с одного запуска с шагом 2 и последнего запуска с шагом 1, и не только алгоритм не сортирует мои элементы, но также дублирует некоторые из них , Вот тестовый код, который выполняется для основной функции 

ArrayList<Integer> l = new ArrayList<Integer>();
l.addAll(Arrays.asList(6,3,7,1,2,4,3));

int     hi,
        m,
        lo;
Integer temp;

for (int s = 2; s > 0; s--)
    for (int i = s; i < l.size(); i += s) { // Binary Insertion sort per-se
        lo = 0; hi = i; m = i/2 + i/2%s; // Added the second term to avoid the mid value being in-between steps

// Binary search part
        do{ if (l.get(i) > l.get(m)) lo = m+s;
            else if (l.get(i) < l.get(m)) hi = m;
            else break;

            m = (lo+(hi-lo)/2) + (lo+(hi-lo)/2)%s;
        } while (lo != m && hi != m);   // The (hi < lo) conditional causes an infinite loop

//Swapping the elements
        if (m < i) {
            temp = l.get(i);
            for (int k = i; k > m; k -= s) l.set(k, l.get(k));
            l.set(m, temp);
        }
    }

System.out.println(l);

Результат println равен

[1, 3, 2, 1, 3, 4, 3]

, тогда как более близкий подход к решению, указанному на указанный сайт (с шагом 1) отсортировал тот же список до совершенства. Что мне делать?

Заранее спасибо!

...