Алгоритмы сортировки

[metaclass]

Народ развлекается забавной задачкой про stl и quicksort.
Заглянув в исходники stl, я понял, что называть это "обычным quicksort" это какое-то явное издевательство.
И еще оказалось, что обычный quicksort из дельфи работает раза в два медленнее чем этот хитрый std::sort, хотя я думаю, кроме всех оптимизаций, там еще косвенный вызов функции сравнения в дельфи свою лепту вносит.

Comments

[x-a-e-p.livejournal.com]

Хотя бы то, что сложность сортировки гарантированно должна быть(по стандарту) O(N*log(N)), говорит о том, что это не quicksort.

[x-a-e-p.livejournal.com]

Ну то есть короче вся проблема в трёх первых словах по линке("Все мы знаем...")

[metaclass.livejournal.com]

Там проблема в том, что rand выдает мало случайных чисел, поэтому после того как размер становится больше чем их количество - линейный рост прекращается.

[familom.livejournal.com]

Как ни странно, но в стандарте только про
Complexity: Approximately N log N (where N == last - first) comparisons on the average
написано.

[x-a-e-p.livejournal.com]

Ну я скорее спорил насчёт quicksort

[tonal.myopenid.com (from livejournal.com)]

по сравнению с делфовой версией там вроде только 2 заметных улучшения:
1. Инлайнинг функции сравнения
2. Сортировка коротких последовательностей с помощью вставок.
Остальное мелкие оптимизации - типа немного разных алгоритмов для граничных и внутренних подпоследовательностей.

Кроме 1-го всё можно без труда повторить на дельфе для конкретного типа.