Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > quicksort vs. mergesort

Автор: Proghat 22.12.2007, 11:48

Что по вашему мнению эффективнее? Что чаще всего пишите вы? Что легче писать и для понимания?

Автор: JackYF 22.12.2007, 12:24

Цитата(Proghat @  22.12.2007,  11:48 ) Что чаще всего пишите вы? Оба алгоритма пишутся один раз, после чего используются. Цитата(Proghat @  22.12.2007,  11:48 ) Что по вашему мнению эффективнее? n*log(n) vs n*log(n). Ну и что эффективнее? Разница в пределах константы. Цитата(Proghat @  22.12.2007,  11:48 ) Что легче писать и для понимания?  Легче написать один раз и забыть, это не те алгоритмы, которые меняются каждый месяц. И тот и другой алгоритм можно понять. С точки зрения реализация, я бы назвал следующие существенные различия: - qsort можно сделать на месте, без использования дополнительно массива - mergesort, зато, сохраняет относительный порядок элементов.

Автор: Proghat 22.12.2007, 13:31

Но ведь qsort за n log(n) в лучшем случае? В худшем же n квадрат? Правильно? P.S. Занимаюсь олимпиадным программированием, поэтому для меня не актуально: Цитата(JackYF @  22.12.2007,  10:24 ) Легче написать один раз и забыть, это не те алгоритмы, которые меняются каждый месяц. Цитата(JackYF @  22.12.2007,  10:24 ) И тот и другой алгоритм можно понять. Ну у них одинаковый принцип работы. Разделение массива на 2 части и сортировка их по отдельности. Но с первого взгляда, мне больше приглянулась сортировка слияние.

Автор: sentry 22.12.2007, 14:05

Цитата(Proghat @  22.12.2007,  13:18 ) Что по вашему мнению эффективнее? Тут мнений быть не должно. От задачи зависит   Цитата(Proghat @  22.12.2007,  13:18 ) Что чаще всего пишите вы? И то, и то (ну не пишу, просто подключаю   ) Потом сравниваю время на наиболее  вероятных данных и выбираю более лучший вариант. Цитата(Proghat @  22.12.2007,  13:18 ) Что легче писать и для понимания? Если не извращаться с оптимизацией, то обе довольно легки и для написания, и для понимания. Цитата(Proghat @  22.12.2007,  15:01 ) В худшем же n квадрат? Правильно? Да. Цитата(Proghat @  22.12.2007,  15:01 ) Но с первого взгляда, мне больше приглянулась сортировка слияние. Ну у слияний есть свои преимущества: устойчивость (уже сказали), сложность не зависит от характера входных данных. А из недостатков могу вспомнить лишь использование дополнительной памяти (уже сказали), пропорциональной N.

Автор: Void 22.12.2007, 14:27

Цитата(Proghat @  22.12.2007,  15:31 ) Занимаюсь олимпиадным программированием Если так, то лучшая сортировка — это встроенная в стандартную библиотеку. Набор алгоритмов и структур данных в стандартной библиотеке экономит тучу времени, поверьте неоднократному участнику ICPC. В моей практике не встречалось случаев, когда разница между быстрой и сортировкой слиянием была бы существенна (за исключением устойчивости), n*log(n) и ладно. Задумываться приходилось лишь о менее универсальных алгоритмах, например, поразрядной сортировке.

Автор: maxdiver 29.1.2008, 23:27

А почему утверждается, что якобы qsort неустойчива? Простейшая модификация, проделанная, например, в стандартной библиотеке C++ (stable_sort), делает её стабильной.

Автор: JackYF 30.1.2008, 00:09

Цитата(maxdiver @  29.1.2008,  22:27 ) stable_sort вообще-то это merge sort ))

Автор: maxdiver 31.1.2008, 10:17

JackYF Афигеть  Просто когда-то читал, что типа stable_sort - это немного модифицированная версия sort, из-за модификаций работающая чуть медленнее...  Спасибо, что просвятили темного человека ))

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)