В попытке достичь красного желтого хотя бы фиолетового цвета, и как следствие, при чтении умной книжки родилась идея провести сравнение различных методов сортировки. Мне кажется, результат может быть интересен сообществу, поэтому привожу сравнительную таблицу. Все сортировки реализованы для массива целых 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. Добавлено более полное описание. Спасибо всем за замечания!
Comments (0)
