Нужна помощь в определении алгоритма целочисленной сортировки

Question

Что это за алгоритм сортировки? Я думал об этом методе вчера вечером и быстро составил код, и, к моему удивлению, сработал отлично. Я просматривал статью в Википедии об алгоритмах сортировки и искал переполнение стека, но не смог найти этот или похожий алгоритм.

Это письменный процесс алгоритма:

[3, 1, 0, 4]
 ^        ^  Check outermost items, swap if necessary
----------------
[3, 1, 0, 4]
 ^     ^     Check first pair of second farthest apart items, swap if necessary
[0, 1, 3, 4]
----------------
[0, 1, 3, 4]
    ^     ^  Check second pair of second farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
 ^  ^        Check first pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
    ^  ^     Check second pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
       ^  ^  Check third pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
             Cannot compare closer items (adjacent), done.

Это алгоритм в JavaScript:

var unsorted = [4, 9, 10, 2, 9, 4, 0];
var sorted = ianSort(unsorted);

function ianSort(array) {
    for(var j = array.length; j > 1; j--) {
        for(var i = 0; i < array.length - j + 1; i++) {
            if(array[i] > array[i + j - 1]) {
                var temp = array[i];
                array[i] = array[i + j - 1];
                array[i + j - 1] = temp;
            }
        }
    }
    return array;
}

(я вызвал функцию IanSort здесь в маловероятном случае, что я первый, кто придумает это. ^ _ ^)

Answer 1

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

Answer 2

Похоже на Расческа

Answer 3

Похоже, это форма алгоритма Comb Sort. Я также подумал, что был первым, кто обнаружил это несколько лет назад, и создал несколько вариантов для проверки быстрой сортировки и других алгоритмов сортировки. Вы можете прочитать о моем исследовании здесь .

Это быстрый алгоритм, который может конкурировать с быстрой сортировкой, даже превосходя ее при некоторых условиях.

Answer 4

Я не совсем уверен, но мне кажется, что алгоритм пузырьковой сортировки .