Comments 28
Но всегда ли QuickSort является «абсолютным чемпионом»?
Нет, не всегда.
Мне вот интересно, вы про timsort слышали?
А Вы первый абзац сообщения прочитали?
Что то вспомнилось выступление Андрея Александреску www.youtube.com/watch?v=FJJTYQYB1JQ Там примерно о том же, но подробнее.
Он еще статью написал, см мой коммент.
А еще есть вариант Квиксорта с разбиением Ломуто, которое, как показано тут в блоге D Александреску, можно сделать с минимизацией условных переходов в коде и выиграть >20%.
Поздравляю, вы открыли адаптивные сортировки, упомянутый timsort как раз из этих ребят.
Сложность QuickSort, тем не менее — n*log(n). ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
Худшее время у него -квадратичное, Вы хотя бы сами читали то, на что ссылаетесь
Худшее — да. Среднее — нет. Я рассматривал QuickSort в выгодной для нее области.
В выгодной области сортировка у меня занимает о(1). Обычно все таки принято указывать худшее время для алгоритмов, а не среднее, когда говорят о теоретической производительности.
Какая универсальная сортировка у вас выполняется за O(1)?
Ну тут все, конечно, можно притянуть за уши.
Есть такая теорема, что если мы считаем QuickSort недетерминированным (случайный выбор элемента для partition на каждом шаге), а потом посчитаем среднее время для всех возможных стартовых сидов этого случайного алгоритма, то мы действительно получим n log(n). Тоесть, в каком-то смысле QS «всреднем» эффективен, а «неудобная область» для него довольно мала.
Но в этом случае:
1) Нужно обговорить что мы имеем ввиду под «показатель производительности». Это может быть и не сложность алгоритма.
2) Нельзя использовать O-нотацию.
3) Вообще, упомянуть эти вещи
Ну и еще могу набросать претензий. А пока статья выглядит как школьная домашняя работа в духе «посмотрите, что я узнал за летние каникулы».
Есть такая теорема, что если мы считаем QuickSort недетерминированным (случайный выбор элемента для partition на каждом шаге), а потом посчитаем среднее время для всех возможных стартовых сидов этого случайного алгоритма, то мы действительно получим n log(n). Тоесть, в каком-то смысле QS «всреднем» эффективен, а «неудобная область» для него довольно мала.
Но в этом случае:
1) Нужно обговорить что мы имеем ввиду под «показатель производительности». Это может быть и не сложность алгоритма.
2) Нельзя использовать O-нотацию.
3) Вообще, упомянуть эти вещи
Ну и еще могу набросать претензий. А пока статья выглядит как школьная домашняя работа в духе «посмотрите, что я узнал за летние каникулы».
Да я знаю, что я не совсем прав, но автор статьи так забавно поставляется под троллинг и так на него ведётся…
А О нотация — это просто нотация. Ей можно характеризовать и теоретическую и практическую производительность, но с оговорками.
Обычно они совпадают и оговорок не требуется.
А статья — да, согласен, школьная. Другие у автора получше.
А О нотация — это просто нотация. Ей можно характеризовать и теоретическую и практическую производительность, но с оговорками.
Обычно они совпадают и оговорок не требуется.
А статья — да, согласен, школьная. Другие у автора получше.
«Ну и еще могу набросать претензий» — у вас, часом, не юридическое образование?
Вообще говоря, теоретически, можно выбирать медиану за O(n) и тогда квиксорт работает за O(n log n) в худшем случае. Этого никто не делает, потому что на практике получается сильно медленнее из-за офигенно большой константы линейного поиска медианы.
Если тупо выбирать случайный pivot, то вероятность быть заметно медленее n log n пренебрежимо мала.
Речь шла о том, что не стоит ссылаться на источник, в котором написано ровно противоположное. А вариация с медианой медиан это все таки не совсем тот же алгоритм., Но интересный, поскольку медиана медиан -это необязательно медиана и как раз медиану за о(п) выбрать таким способом не получится. Так что читайте внимательней источники :)
Sign up to leave a comment.
Цена естественности или как обогнать QuickSort