Как работает алгоритм ShellSort?

Question

[Den4_x]

public static void shellSort(int[] array) {

        int step = array.length / 2;

        while (step != 0) {
            for (int i = 0; i < step; i++) {
//Как может работать сл-ий цикл, если тут j в последствии выходит за индексные рамки массива?
                for (int j = i + step; j < array.length; j += step) {

                    int temp = array[j];
                    int k;
//Тот же вопрос
                    for (k = j - step; k >= 0 && array[k] > temp; k -= step) {
                        array[k + step] = array[k];
                    }
                    array[k + step] = temp;
                }
            }
            step = step / 2;
        }

    }

Суть алгоритма ясна, тот же InsertionSort только тут интервал добавили. Но вот с этими двумя строками кода, я немного не понял (см. выше). В чем тут прикол?

Answer 1

[Дмитрий Шицков]

Каким образом он выходит за индексные рамки массива, если условие цикла
j < array.length
?

Comments

[Den4_x]

А как можно узнать, время выполнения этой сортировки в мс?

[Дмитрий Шицков]

Den4_x, https://ru.stackoverflow.com/questions/608818/%D0%...

[Den4_x]

Дмитрий Шицков, спасибо огромное