Сортировка массива при помощи бинарного дерева

Цитата Kheor, 29.11.04, 22:22, 527418

qsort в среднем работает ~ в 4 раза быстрее сортировки кучей

Во многом благодаря тому, что все операции очень простые (тоже из олимпиадной практики).
Где-то читал, что хорошо себя проявляет модификация quicksort-а, где при небольшом количестве элементов (порядка 10) используется сортировка вставками...

Цитата tserega, 30.11.04, 22:02, 528700

Где-то читал, что хорошо себя проявляет модификация quicksort-а, где при небольшом количестве элементов (порядка 10) используется сортировка вставками...

Кхм, скорее всего оно действительно станет работать быстрее, но код резко усложнится, а при количестве порядка 10^5 - 10^6 элементов, это вряд ли сильно повлияет на скорость, хотя надо попробовать

PS Опять таки из олимпиадной практики: достаточно написать обычный qsort и будет счастье =)

Госопода, так ведь существует же обыкновенный метод сортировкм с помощью дерева! Это тот, когда мы выбираем из соседних пар меньший ключ и т.д., пока не найдем наименьший элемент. В связи с этим у меня вопрос. После того, как дерево построено и мы начинаем обход, то при спуске мы должны сотворить log n
сравнений(чтобы понимать, куда идтить, влево или вправо). После того, как мы заменяем один из элементов массива(наименьший из сущ.) на "дыру", мы должны скорректировать дерево и подняться наверх. для этго ведь тоже надо log n сравнений! Всего получаем 2log n*n Почему же везде пишут, что их log2*n? Объясните мне, пожалуйста! Да, я еще прогу неотлаживал, однако в случае нечетного кол-ва элементов алгоритм сохраняется?Я думаю, что да, а вы?

Сообщение отредактировано: Ярослав - 20.04.05, 20:17