SkyHawk's blog

By SkyHawk, 10 years ago, In Russian

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

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

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

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

В планах: 

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

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

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

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

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

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

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it