bottom-up heapsort

bottom-up heapsort
5 1 чел.

Ненайдя промышленной реализации метода сортировки bottom-up heapsort, решил реализовать этот алгоритм самостоятельно, с небольшой модификацией.

Исходный код можно посмотреть на Github: github.com/Maxime2/heapsort

Bottom-up heapsort (bottom-up-heapsort) является вариантом алгоритма сортировки heapsort (пирамидальной сортировки) с новой процедурой восстановления пирамиды. Этот варианд превосходит, в среднем, алгоритм быстрой сортировки (quicksort), если n > 2400, и модифицированный вариант быстрой сортировки с выбором ведущего элемента как медианы 3 элементов массива, если n > 16000.

Алгоритм bottom-up heapsort описан в работе Ingo Wegener, BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small), Theoretical Computer Science 118 (1993), pp. 81-98, Elsevier.

Добавленная мной модификация, позволяющая дополнительно сэкономить (n-2)/2 операций обмена и (n-2)/2 операций сравнения, при n > 3, основана на идее отложенного восстановления пирамиды после перемешения корневого элемента на его место, найденной в работе D. Levendeas, C. Zaroliagis, Heapsort using Multiple Heaps, in Proc. 2nd Panhellenic Student Conference on Informatics -- EUREKA. – 2008. – P. 93–104.

Поделиться:
  • Twitter
  • LiveJournal
  • Блог Я.ру
  • Блог Li.ру
  • Google Buzz
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Одноклассники
  • Facebook
  • FriendFeed
  • В закладки Google
  • LinkedIn
  • StumbleUpon
  • Technorati
  • Digg
  • БобрДобр
  • MisterWong.RU
  • Memori.ru
  • МоёМесто.ru
  • Сто закладок

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *