Сортировка расческой. Что такое число 1.247?

Question

[urfeick]

Что такое число 1,247? Почему именно это число, а не какое-то другое, используется в сортировке расческой и как оно влияет на обход массива? Формула: 1,247 = 1/(1-e^(-φ))

Comments

[Сергей Соколов]

в англоязычной статье на wiki предлагают фактор в 1.3, ссылаясь, что именно такое значение предлагали авторы первой публикации этого алгоритма.

в русскоязычной статье же предлагается упомянутый фактор 1.247 Пишут, что он получен эмпирически (опытным путем), и без ссылки на источник.

[Alexandroppolus]

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

[mayton2019]

Напоминает сортировку Шелла. Там тоже были магические числа которые автор рекомендовал как оптимальный выбор шага.

Да вообще-то какая разница откуда взято это число? Оно могло быть подобрано просто численным методом исходя из оптимального числа копирований и записей.

Вобщем ну ее в болото. На собеседовании все равно не спросят ибо никто не знает.

[urfeick]

mayton2019, да мне и не для собеседования это надо, просто в унике проходили разные сортировки, в том числе и это. Когда искал инфу, заметил, что непонятное число, а в вики вообще дают какую то магическую силу в виде "фактора уменьшения", поэтому и спросил.

[mayton2019]

urfeick, в программировании много магических чисел. Золотые и бронзовые сечения... Тьфу. Это теоретики "туману напускают". Им же надо свои докторские работы защитить.

[Wataru]

Alexandroppolus, Сортировка корректно работает при любом факторе (больше 1). Это все тот же пузырек же в итоге. Хоть и делается сколько-то необычных итераций в начале.

[Alexandroppolus]

Wataru, проверил, уже при 1.6 не сортируется 1000 элементов (исходно расположенных в обратном порядке).

вообще я сильно подозреваю, что числа e и Ф там не просто так вылезли.

----
и кстати нихрена не понятно, откуда там квадратичное время в "худшем кейсе" (если верить википедии). Очевидно, у внешнего цикла всего логарифм итераций.

[Wataru]

Alexandroppolus, у вас там флаг в условии while есть? Без него при любом факторе есть не сортируемые массивы.

[Alexandroppolus]

Wataru, какой флаг?
я просто взял код из русской википедии (js, он такой же как в с++), и поменял "магическое число" на 1.6

[Wataru]

Alexandroppolus, И там хрень в русской википедии. Сравните код в русской и английской. Действительно, то, что в русской написано - O(n log n) и не всегда работает.

Надо, когда step==1 все-равно гнать цикл, если на предыдущей итерации что-то поменялось.

[Wataru]

Alexandroppolus, Или код на питоне и С++ сравните. Первый правильный, второй - фигня. Для php там вообще тупо пузырек в русской википедии написан. Плохая статья.

[Alexandroppolus]

Wataru, да, действительно. Ох уж эта википедия..

Как назло, ещё и в гифке всё так удачно сходится )

Answer 1

[Wataru]

Судя по всему, это число вылезло в результате эксперементов каких-то исследователей. Они просто попробовали кучу разных факторов и нашли что при 1.247 вроде как быстрее в среднем. Формулу по это число потом какой-то шутник придумал. Кроме как в русской википедии (без ссылки на источник) я нигде эту формулу найти не могу.

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