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

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

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