Сравнение популярных сортировок

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

В попытке достичь ~~красного желтого~~ хотя бы фиолетового цвета, и как следствие, при чтении умной книжки родилась идея провести сравнение различных методов сортировки. Мне кажется, результат может быть интересен сообществу, поэтому привожу сравнительную таблицу. Все сортировки реализованы для массива целых 32-битных чисел.

Название	О(...)	Данные	Время(c)	Код	Описание
Выбором	n²	10⁴	0.04	link	link
Пузырьковая	n²	10⁴	0.22	link	link. Устойчивая. Плюсы: легка для написания.
Пузырьковая (опт.)	n²	10⁴	0.23	link	Добавлен сторожевой элемент (вообще можно добавить много оптимизаций, только толку от них не много =) )
Вставками	n²	10⁴	0.04	link	link Эффективна на маленьких наборах. Устойчивая.
Быстрая	n*logn	10⁶	0.16	link	link.Неустойчивая сортировка.В худшем случае работает за О(n²). Тратит О(log n) памяти (в худшем случае О(n))
С++ sort	n*logn	10⁶	0.11	link	Встроенная в С++ STL сортировка.
С++ stable_sort	n*(logn)²	10⁶	0.14	link	Её устойчивая версия. При достаточном объеме дополнительной памяти работает за О(n*logn)
С qsort	n*logn	10⁶	0.36	link	Встроенная в Си сортировка
Слиянием	n*logn	10⁶	0.37	link	link Устойчивая сортировка. Расходует О(n) памяти.
Слиянием(опт.)	n*logn	10⁶	0.16	link	Оптимизация выделения памяти и использование сортировки вставками для маленьких подмассивов.
Пирамидальная (HeapSort)	n*logn	10⁶	0.3	link	link Требует О(1) дополнительной памяти, строит сортирующее дерево, которое можно использовать для других целей. Неустойчива.
Поразрядная	n*sizeof(int)	10⁶	0.03	link	link. Числа сортируются побайтно. Требует О(n) памяти.
Блочная (BucketSort)	n	10⁶	0.2	link	link. Корзины реализованны как списки на основе массива целых чисел. Требует О(n) памяти.
Рандомная =)	n*n!	10	0.02 - 3	link	link.

Здесь лежат все файлы единым архивом, make-файлом и тестирующей программой для проверки сортировок.

Компилировал с опциями оптимизации под Linux: g++ -march=native -static -O3 -c filename.cpp

В планах:

Реализовать сортировки для списков и строк.
Научиться писать нормальные makefile'ы
Написать Natural Merge Sort

Хотелось бы увидеть:

Советы по реализации и оптимизации алгоритмов
Более качественные версии ваших любимых сортировок.
Нормальный BucketSort (радиус кривизны моих рук не позволяет написать это)

Заранее спасибо за комментарии и удачи на предстоящем Beta Round!

P.S.Напоследок: SleepSort =)

UPD. Добавлено более полное описание. Спасибо всем за замечания!

Комментарии (78)

Показать архивные | Написать комментарий?

Depool

13 лет назад, # |

← Rev. 2 →

Интересный материал:) На мой взгляд, было бы неплохо добавить в таблицу для каждой сортировки ее преимущества и недостатки по сравнению с другими.

Не знаю как на С++, но на Паскале строки сортируются так же как и массивы чисел.

→ Ответить

daftcoder

13 лет назад, # ^ |

Угу, например мин/макс/среднюю асимптотику, возможно примеры входных данных для крайних случаев, является ли сортировка stable. Может ещё что-то.

SkyHawk

Строки - понятно что так же, но сравнение строк - операция довольно дорогая. С другой стороны, при попытке использовать поразрядную сортировку асимптотика составит О(n*k), где k - длина строк, что при маленьком количестве длинных строк будет накладно. Поэтому результат может отличаться.

IlyaLos

Интересная задумка.

Не знаю, видели вы или нет, но на Вики есть очень подробный материал об очень многих сортировках., включая описание их преимуществ и недостатков. Можно использовать, как начальную базу для собственных проверок.

Интересно будет проверить их эффективность в реализации для списков. Про это мало где пишут, а задача порой важна.

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

Да, эта таблица скорее для начинающих. К коим я и себя отношу =) Но на мой взгляд даже здесь можно почерпнуть чего-нибудь интересного, например превосходство разрядной сортировки, а также то, что стандартная сортировка настолько эффективна.

vsb	13 лет назад, # \| 0 Не очень понятно, почему "Блочная (BucketSort)" имеет асимптотику O(n). Кто-нибудь может объяснить подробно? → Ответить

Skird

Она вроде имеет асимптотику O(n) только в том случае, когда входные данные случайны. В Кормене есть доказательство ожидания времени работы на массиве случайных дробных чисел от 0 до 1.

tunyash

Нет, не асимптотику. Это ожидаемое время работы на ~~случайно~~ равномерно распределенных входных данных. Асимптотика, вроде бы, O(n²)

freopen

+12

Вам будет интересно узнать, что стабильная сортировка работает за время $\text{[math]}$ . Пруф: 1,2,3

yahooo

-8

наверное стандартная сортировка быстрее за счет того что идет работа с указателями...

А почему коммент к моему сообщению?

ну как бы в принципе встроенный сорт работает дольше чем NlogN и по идее время работы должно занимать больше, а получается наоборот... вот как бы поэтому и к вашему

PavelKunyavskiy

Он очень прямо написан. И я думаю что все таки Nlogn хотя бы в среднем. Там даже всякая магия типа если мы очень маленькие то разберем ручками (например для 5 можно 7 сравнений), если просто маленькие то вставками, иначе Qsort. А если мы как-то глубоко ушли в рекурсию, то толи merge сорт толи heap сорт запускается вроде. Хотя может все это легенды, но 5 миллионов чисел сортирует спокойно за секунду. (во всяком случае, я помню что где-то такое сдавал)

nk.karpov

На ночь глядя такой вопрос, а как выбор опорного в стандартной сортировке stl реализован с помощью медиан или рандома?

Philip_PV

stl::sort работает за $\text{[math]}$ в худшем случае в большинстве реализаций (ms, sgi, stlport), ибо там не qsort, а introsort.

Спасибо! Не вдавался в этот вопрос, сейчас исправлю.

-18

А ваша быстрая за n² в худшем случае работает. Надо писать быструю с выбором случайного элемента, а не среднего.

Это-то понятно, но вроде как классический вариант быстрой... Зато теперь для неё не трудно построить пример худшего случая =) И если честно, я её просто не люблю.

Я про то, что у вас в таблице об этом не написано. А это кажется важным.

Тогда наверное стоит для всех сортировок указать время работы на худшем случае.

Кажется, это единственное место, требующее изменения.

Sergey.Bankevich

Взятие случайного элемента сложность не изменит.

Тест будет уже не подобрать просто так. Однако, зная устройство рандома и сид, это можно сделать. И в любом случае то, что тест не подобрать, не значит, что его нет. А он есть.

primorial

Сложность худшего останется, да, но вот вероятность наступления такого случая становится ничтожно мала. Введение случайной величины приводит к тому, что худший случай перестаёт зависеть от строения входных данных и теперь зависит лишь от генератора. В данном случае, вы уже не тест подбираете, а изменяете условия окружения.

Вы не правы. Если при равномерном распределении входных данных взять вероятность плохого исхода или просто распределение времени выполнения сортировки, то переход к случайному выбору медианы не изменит ничего. Поэтому, если все большие тесты жюри рандомные и программа прогоняется один раз, то шансы пройти у неё тоже не меняются. Вероятно, предположение про жюри можно заменить условием, что они не пытаются специально завалить конкретную реализацию сортировки (что обычно так). В таком случае на олимпиаде вообще нет разницы, какой метод использовать.

=============================================

Кхм, посмотрите, пожалуйста, ещё раз, внимательнее, на то, что я писал. Я пока не могу видеть момента в моём сообщении, в котором я явно не прав.

Дело, вроде же, было так:

1) Вы говорите про подбор теста для деградации

2) Я говорю, что при введении случайной велчины худший случай перестаёт явно зависеть от конкретного строения входных данных

3) Вы говорите про равномерное распределение входных данных

В последнем случае - да, рандомизация не улучшит ситуацию, но, надо заметить, что до этого вашего сообщения в предыдущем обсуждении не было речи о равномерном распределении, а лишь о конкретном "валящем" тесте.

Вообще, рандомизация вводится как раз из тех соображений, что в жизни некоторые, нехорошие для быстрой сортировки, входные данные могут попадаться чаще других. Рандомизация, как я это себе преставляю, как бы уравнивает все входные данные, превращая их в, словно бы, равномерно распределённые. Могу, конечно, ошибаться, но вроде же всё так.

abzaloid

-16

Не хочу засорять прямой эфир. Кто может написать на java такую задачу: даны два числа (a,b<=2^(10000)). надо найти a xor b.

Все не надо. Спасибо. Сам догадался)

Надо начать чуть раньше.

freopen написал такую фразу, из которой можно было бы сделать вывод, что введение случайности меняет трудоёмкость.

Основной смысл моего комментария был в том, что это не так. Трудоёмкость остаётся прежней. В подтверждение своей точки зрения я сказал, что можно подобрать тест. Точнее, подбирать его никто не собирается, просто он существует.

Следующий мой комментарий был возмущением по поводу вашей фразы "вероятность наступления такого случая становится ничтожно мала". Формально она неверна, что я и попытался показать.

По поводу вашего последнего замечания. Может, это и так, но, поскольку в среднем быстрая сортировка всё-таки работает за O(n log n), доля количества плохих тестов не более O(log n/n), то есть немного. Плюс ещё два субъективных аргумента. Мне кажется, у плохих тестов не такая простая структура, чтобы они хоть сколь-нибудь часто попадались на соревнованиях. За несколько лет студенческих олимпиад, что мне приходилось писать сортировку вручную, ни разу подлян не было.

Резюме. На олимпиадах можно использовать, если хочется перестраховаться. Формально трудоёмкость всё равно O(n²).

А я налетал на antiqsort 3 или 4 раза.

Ясно. Но это называется именно подляна. Не ясно, чем может руководствоваться жюри, давая такие тесты. Разве что самолюбие потешить.

Да, но это кажется в порядке вещей. Если жюри предполагает, что есть случай на который у кучи участников будет завал даже в правильном алгоритме (крайний случай, переполнение и т.п.), неужели жюри не даст тест на такой случай?

Только в том случае, если очень гордится, что его разобрало само. Это стандартный алгоритм, все знают его свойства. Задача жюри обеспечить качественное black-box тестирование, а не давать странное преимущество одному правильному решению перед другим. Я привык к такому пониманию роли жюри.

Скажите, а как вы относитесь к взломам и челленжам?

Как к white-box тестированию. То есть да, если код будут смотреть, то не стоит писать без случайного выбора. Если вас почелленджили антикусортом, я в этом ничего страшного не вижу в отличие от заготовленных заранее тестов.

Ясно, спасибо за развернутый ответ.

riadwaw

===================================

А не считаете ли вы плохим, что одинаковые решения в разных комнатах могут быть зачтенным у одного и незачтенным у другого?

yeputons

Это уже вопрос к создателям системы, как мне кажется.

А что если я делаю qsort опираясь на встроенный в паскаль rand, а мой оппонент подобрал тест против рандома в паскале?

imslavko

___шире___пожалуйста____________________________________________

вроде, паскалисты в начале randomize прописывают. Не знаю, является ли это эквивалентом srand(time(null)) в C++?

==================================
Но это же бред. Т.е. любая ошибка в qsort, включая вот такую тупость дает возможность меня челленжить.

FunnyWarp

==============================
>ошибка дает возможность меня челленжить
>бред

=====================
Ваши сообщения через чур лаконичны. Что имелось в виду? Я имею в виду, что есть малый процент участников, которые подготовили тест против qsort с рандомизацией но без случайной инициализации рандома (что оправдано в других олимпиадах, ведь жюри может перетестировать решение и зачесть худший из результатов), эти участники должны получить преимущество перед остальными? А среди них те, кто попал в комнату к большому количеству паскалистов? Как то оно не слишком здорово.

dalex

===========================
Я так понимаю, скоро все взломы будут добавляться в систесты.
Так что паскалистам придется писать heapsort или mergesort (почему они не делают этого всегда?)

==================================

У системы с комнатами и челленджами есть много недостатков, связанных со случайным/недостаточно честным разбиением. Это не имеет отношения к проблемам qsort.

==========================

Про вероятность плохого случая и контекст, в котором это говорилось, я уже писал раньше.
А по поводу написания быстрой сортировки на студенческих олимпиадах:

Сейчас это уже, имхо, лишнее (stl-вский sort вполне хорош (он, если не ошибаюсь, в основных реализациях представляет собой introsort или что-то похожее), у Java, если не ошибаюсь, со встроенной сортировкой тоже хорошо). Я ни в коем случае не утверждаю, что её не нужно знать и понимать, и уметь написать. Но писать каждый раз с нуля - ненужная роскошь.

А, ещё, в легенды СП уже, наверное, вошла история про то, как на одном из соревнованийбыл подобран тест под qsort из Си и по этой причине упала задача у Petr.

Ну я и не говорю, что его надо писать. Сейчас такая ситуация только у школьников, наверное.

Про Пету я слышал другую версию. Это были шарпы, а тест был типа сколько-то возрастающих чисел, потом сколько-то убывающих. Так что это беда конкретной реализации в языке, которой, и правда, непозволительны подобные промахи.

AndrewLazarev

Там тест был не специально такой. Просто оказалось, что на тесте "1 2 ... n n ... 2 1" стандартный qsort работает за O(n^2). Желающие могут доказать.

NKolotey

А где это было? На каком-то SRM? Детали какие-нибудь где-нибудь можно посмотреть?

Это был финал ttb (Test-The-Best) в Минске. Видимо, единственный. Видимо, в 2007.

=========================================================================

К сожалению найти результаты и тесты не удалось. Но правильно ли я понял, что под "это были шарпы" подразумевался C#? Или задача так назвалась? Просто поскольку это мой рабочий язык хотя бы знать чего опасаться. Затестил под дотнетом 4 сортировку 1 2 3..n n...3 2 1 - вроде бы одинаково шустро работает как в таком виде, так и после случайного вбзалтывания.

http://pastebin.com/hSTwkqyy

Да, C#. По слухам уже исправили, сам не знаю. Найти скорее всего и не удастся, они прикрылись.

sweiss

если мне не изменяет память, это было какое-то финальное соревнование TTB

← Rev. 3 →

Это только если не получится выделить O(n) дополнительной памяти для merge sort (который работает за $\text{[math]}$ ), тогда оно переключается на in-place merge sort ( $\text{[math]}$ ), что, кстати, и написано в приведенных Вами ссылках (и в Стандарте: 25.3.1.2).

Думаю, для стандартного применения можно считать, что памяти хватит :)

кст, рандомная сортировка реализована немного криво, например на массиве 1, 1, 1 она тлится

+17

А где GoroSort, почему не упомянут? :)

он только для перестановок...

Но его можно расширить и для произвольных массивов.

djrock

Хотелось бы увидеть Гномью Сортировку!А чем отличается с++ qsort и быстрая сортировка, не считая времени Работы! Разве не один и тот же алгоритм?

Если вы говорите про std::sort (а не std::qsort), то он ведёт себя примерно так:

Если n ≤ 3, то разбираем руками за три сравнения.
Далее пускаем хорошо написанный qsort
Если он углубился слишком сильно - heapsort.

Ага т.е лучше использовать std::sort!? а как тогда ведёт себя std::qsort?

Да. У меня один знакомый пытался обогнать sort на больших массивах - не получилось.
Как себя ведёт qsort, увы, не знаю.

кстати, раз уж речь зашла о сортировках, на каком тесте, например для 10, быстрая сортировка будет работать N^2?

Вроде как 1 3 5 7 9 10 6 4 8 2

Если выбирается элемент a[(l+r)/2], то, например, 1 4 6 8 10 5 3 7 2 9.

Это у меня генератор припасен для любителей quicksort-а :)

it4.kp

У вас генератор работает для любой детерминированной функции выбора среднего элемента или только для (l+r)/2?

Просто существует простой способ написать генератор для любой.

Вообще я знаю, как делать для любой функции. Ссылку прочту

goo.gl_SsAhv

Вообще имеет смысл сравнивать для сортировок не только время работы, но и количество сравнений. так например для тяжёлой функции сравнения Merge sort будет круче чем qsort, std::stable_sort круче чем std::sort.

А какой алгоритм у std::stable_sort?? чем она круче std::sort?

по моему там как раз MergeSort, круче тем что во первых она стабильная (для одинаковых элементов сохраняется их исходный порядок, а вто вторых сравнений меньше делает.

AlexSkidanov

Давно было интересно -- а существует сортировка, которая обладает следующими характеристиками:

1. Время худшее: O(N log N) -- пусть даже с очень тупо завышенной константой

2. Память худшая: O(1)

3. Stable

или нет?

maksay

Третий пункт можно убрать, заменив число X на i-той позиции на упорядоченную пару {X,i}. Или считается, что это уже О(N) дополнительной памяти?

heap sort, если не ошибаюсь на счет стабильности, обладает всеми тремя свойствами.

да, я ошибся, хипсорт не стабилен.

вот тут описывается стабильный алгоритм слияния "на месте", и сортировка слиянием требующая константу памяти (если рекурсию развернуть то стек не надо юзать).

Да, похоже на правду. Спасибо.

AlexanderBolshakov

← Rev. 5 →

Хипсорт с расширенным ключом стабилен.

UPD. На расширение ключа требуется O(n) дополнительной памяти, так что я ошибся.

Блог пользователя SkyHawk