В попытке достичь красного желтого хотя бы фиолетового цвета, и как следствие, при чтении умной книжки родилась идея провести сравнение различных методов сортировки. Мне кажется, результат может быть интересен сообществу, поэтому привожу сравнительную таблицу. Все сортировки реализованы для массива целых 32-битных чисел.
| Название | О(...) | Данные | Время(c) | Код | Описание |
| Выбором | n2 | 104 | 0.04 | link | link |
| Пузырьковая | n2 | 104 | 0.22 | link | link. Устойчивая. Плюсы: легка для написания. |
| Пузырьковая (опт.) | n2 | 104 | 0.23 | link | Добавлен сторожевой элемент (вообще можно добавить много оптимизаций, только толку от них не много =) ) |
| Вставками | n2 | 104 | 0.04 | link | link Эффективна на маленьких наборах. Устойчивая. |
| Быстрая | n*logn | 106 | 0.16 | link | link.Неустойчивая сортировка.В худшем случае работает за О(n2). Тратит О(log n) памяти (в худшем случае О(n)) |
| С++ sort | n*logn | 106 | 0.11 | link | Встроенная в С++ STL сортировка. |
| С++ stable_sort | n*(logn)2 | 106 | 0.14 | link | Её устойчивая версия. При достаточном объеме дополнительной памяти работает за О(n*logn) |
| С qsort | n*logn | 106 | 0.36 | link | Встроенная в Си сортировка |
| Слиянием | n*logn | 106 | 0.37 | link | link Устойчивая сортировка. Расходует О(n) памяти. |
| Слиянием(опт.) | n*logn | 106 | 0.16 | link | Оптимизация выделения памяти и использование сортировки вставками для маленьких подмассивов. |
| Пирамидальная (HeapSort) | n*logn | 106 | 0.3 | link | link Требует О(1) дополнительной памяти, строит сортирующее дерево, которое можно использовать для других целей. Неустойчива. |
| Поразрядная | n*sizeof(int) | 106 | 0.03 | link | link. Числа сортируются побайтно. Требует О(n) памяти. |
| Блочная (BucketSort) | n | 106 | 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. Добавлено более полное описание. Спасибо всем за замечания!
случайноравномерно распределенных входных данных. Асимптотика, вроде бы, O(n2)Но это же бред. Т.е. любая ошибка в qsort, включая вот такую тупость дает возможность меня челленжить.
>ошибка дает возможность меня челленжить
>бред
Ваши сообщения через чур лаконичны. Что имелось в виду? Я имею в виду, что есть малый процент участников, которые подготовили тест против qsort с рандомизацией но без случайной инициализации рандома (что оправдано в других олимпиадах, ведь жюри может перетестировать решение и зачесть худший из результатов), эти участники должны получить преимущество перед остальными? А среди них те, кто попал в комнату к большому количеству паскалистов? Как то оно не слишком здорово.
Я так понимаю, скоро все взломы будут добавляться в систесты.
Так что паскалистам придется писать heapsort или mergesort (почему они не делают этого всегда?)
А по поводу написания быстрой сортировки на студенческих олимпиадах:
Как себя ведёт qsort, увы, не знаю.
Это у меня генератор припасен для любителей quicksort-а :)
Просто существует простой способ написать генератор для любой.