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

[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
написано.