Тёмная тема
- Suslik
- Участник
FordPerfect
0.8397803045, если быть более точным)
ну, понеслася
http://habrahabr.ru/post/247053/
FordPerfect
> http://www.codecogs.com/latex/eqneditor.php
в нём удобно формулу набирать и сразу смотреть результат, тегом cht её отображать. потом, если захочется поредактировать, то формула будет сразу в сообщении в текстовом виде. но вообще codecogs - очень удобная штука.
Suslik
Если б они ещё были совсем идентичны (bug-compatible) - была бы вообще песня.
R.I.P.
Неужели асимптотика ухудшается до O(n2n) для нашего Median of Medians (и до O(n3n) для всего алгоритма)? Тут все несколько сложнее.
Это точно то, что ты хотел написать?
FordPerfect
> Это точно то, что ты хотел написать?
нет, куда-то потерял логи, поправил, спасибо.
> а так же в Кормене,
так же -> также
>Описание алгоритм Median of Medians
алгоритм -> алгоритма
И в конце непонятный заголовок "Код".
kipar
за опечатки спасибо, поправил
заголовок "Код" обозначает раздел, где собраны все ссылки на код
Известные сортировки, которые сразу приходят на ум, не удовлетворяют всем трем пунктам, например:
Неоднозанчно парсится.
И по-умолчанию, думаю, парсится некорректно.
Мануель Блюм, Роберт В Флойд, Вон Пратт, Рональд Л Ривест и Роберт Е Тарьян.
Роберт В Флойд нормально, а вот остальным бы точки поставить, а?
FordPerfect
> Неоднозанчно парсится.
> Роберт В Флойд нормально, а вот остальным бы точки поставить, а?
fixed
Mrrl с хабра выложил код in place merge sort, адаптированной под последовательный доступ
http://habrahabr.ru/post/247053/#comment_8213001
ripatti 7 января 2015 в 00:09 # ↵ ↑
Боюсь, она медленнее сортировки слиянием для любого количества элементов. Даже тесты делать руки опускаются.
Вообще говоря, всё на удивление хорошо.
Ну или я накосячил с тестом:
http://www.everfall.com/paste/id.php?x4qujue6vag1
Результат:
http://www.everfall.com/paste/id.php?ir8s86woo7f9
Некоторые наблюдения:
1. При времени работы существенно больше гранулярности таймера - flat quick sort стабильно быстрее insertion sort.
2. При этом же условии - время заполнения исходных данных - намного больше собственно сортировки.
И это ещё повезло, что у std::list::push_back - время работы константное.
У std::forward_list push_back нет вообще.
Ибо нефиг.
С std::sort не сравнивал.
FordPerfect
Я подобные тесты тоже проводил
Там insertion sort чуть быстрее только в окрестности 3500
С обычным sort сравнивать мало смысла:
Для 1 000 000 обычный сорт укладывается в 1 сек, эта же реализация работает порядка 40 секунд
R.I.P.
Какой бы мы pivot не вернули, flat_quick_sort в любом случае работает не хуже квадратичного (если сам pivot ищется быстро).
Поэтому использовать квадратичную сортировку для n<3500 не обязательно.
if (n<3500) { //insertion_sort( be, en ); return ::next( be, n/2 ); }
Если не ошибаюсь.
Тест:
http://www.everfall.com/paste/id.php?fvq4o8ip0442
Отчёт:
http://www.everfall.com/paste/id.php?g2wqrwmpsinh
Результат: в 10 раз медленнее std::sort.
А Mrrl крут, конечно.
Тема в архиве.