Сортировка - Splaysort

В Информатика, splaysort является адаптивный сравнительная сортировка алгоритм на основе растопленное дерево структура данных.[1]

Алгоритм

Шаги алгоритма:

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

Таким образом, алгоритм можно рассматривать как форму вставка сортировки или же сортировка по дереву, используя расширяемое дерево для ускорения каждой вставки.

Анализ

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

Для входной последовательности, в которой большинство элементов размещено рядом с их предшественниками в отсортированном порядке или не в порядке только с небольшим количеством других элементов, splaysort может быть быстрее, чем О(п бревноп), показывая, что это адаптивная сортировка. Чтобы выразить это количественно, позвольте dИкс быть количеством позиций во входных данных, разделяющих Икс от своего предшественника, и пусть яИкс быть количеством элементов, которые появляются на одной стороне Икс на входе и с другой стороны Икс на выходе (количество инверсии которые включают Икс). Тогда из теоремы о динамическом пальце для растянутых деревьев следует, что общее время сплайсорта ограничено

и по

.[2]

Также можно показать, что сортировка по сортировке адаптируется к энтропия входной последовательности.[3]

Результаты экспериментов

В экспериментах Моффат, Эдди и Петерссон (1996), splaysort был медленнее, чем quicksort для таблиц случайных чисел в 1,5–2 раза, и медленнее, чем mergesort, в меньшем размере. Для данных, состоящих из более крупных записей, опять же в случайном порядке, дополнительный объем перемещения данных, выполняемый быстрой сортировкой, значительно замедлил ее по сравнению с алгоритмами на основе указателей, а время для splaysort и mergesort было очень близко друг к другу. Однако для почти предварительно отсортированных входных последовательностей (измеряемых в терминах числа смежных монотонных подпоследовательностей в данных, числа инверсий, числа элементов, которые должны быть удалены для создания отсортированной подпоследовательности, или числа несмежных монотонных подпоследовательностей на которые можно разделить вход) splaysort стал значительно более эффективным, чем другие алгоритмы.[1]

Элмасри и Хаммад (2005) сравнил splaysort с несколькими другими алгоритмами, которые адаптируются к общему количеству инверсий на входе, а также с быстрой сортировкой. Они обнаружили, что на входах, у которых было достаточно мало инверсий, чтобы адаптивный алгоритм работал быстрее, чем быстрая сортировка, splaysort был самым быстрым алгоритмом.[4]

Вариации

Сайкконен и Сойсалон-Сойнинен (2012) изменить splaysort, чтобы он был более адаптивным к количеству непрерывных монотонных подпоследовательностей во входных данных, и отчет об экспериментах, показывающих, что результирующий алгоритм работает быстрее на входах, которые почти предварительно отсортированы в соответствии с этой мерой.[5]

Рекомендации

  1. ^ а б Моффат, Алистер; Эдди, Гэри; Петерссон, Ола (июль 1996 г.), «Сортировка: быстро, универсально, практично», Практика и опыт работы с программным обеспечением, 26 (7): 781–797, Дои:10.1002 / (SICI) 1097-024X (199607) 26: 7 <781 :: AID-SPE35> 3.3.CO; 2-2
  2. ^ Коул, Ричард (2000), "О гипотезе динамического пальца для растянутых деревьев. II. Доказательство", SIAM Журнал по вычислениям, 30 (1): 44–85, CiteSeerX  10.1.1.36.2713, Дои:10.1137 / S009753979732699X, МИСТЕР  1762706.
  3. ^ Гэги, Трэвис (2005), Сортировка низкоэнтропийной последовательности, arXiv:cs / 0506027, Bibcode:2005cs ........ 6027G.
  4. ^ Элмасри, Амр; Хаммад, Абдельрахман (2005), "Эмпирическое исследование чувствительных к инверсиям алгоритмов сортировки", Экспериментальные и эффективные алгоритмы: 4-й международный семинар, WEA 2005, остров Санторини, Греция, 10-13 мая 2005 г., Труды, Конспект лекций по информатике, 3503, Springer, стр. 597–601, Дои:10.1007/11427186_52.
  5. ^ Сайкконен, Рику; Soisalon-Soininen, Eljas (2012), "Общий метод улучшения адаптивной сортировки на основе вставки", Алгоритмы и вычисления: 23-й международный симпозиум, ISAAC 2012, Тайбэй, Тайвань, 19-21 декабря 2012 г., Труды, Конспект лекций по информатике, 7676, Springer, стр. 217–226, Дои:10.1007/978-3-642-35261-4_25.