Сплейсорт
В информатике , splaysort — это адаптивный сортировки сравнения алгоритм основанный на дерева расширения структуре данных . [1]
Алгоритм
[ редактировать ]Шаги алгоритма следующие:
- Инициализировать пустое дерево воспроизведения
- Для каждого элемента данных во входном порядке вставьте его в дерево отображения.
- Перейдите по дереву расширения , чтобы найти отсортированный порядок данных.
Таким образом, алгоритм можно рассматривать как разновидность сортировки вставками или древовидной сортировки , в которой используется расширенное дерево для ускорения каждой вставки.
Анализ
[ редактировать ]На основании амортизированного анализа расширенных деревьев, наихудшее время выполнения расширенной сортировки для входных данных с n элементами данных равно O ( n log n ), что соответствует временным границам для эффективных неадаптивных алгоритмов, таких как быстрая сортировка , пирамидальная сортировка , и сортировка слиянием .
Для входной последовательности, в которой большинство элементов расположены близко к их предшественникам в отсортированном порядке или находятся не в порядке с небольшим количеством других элементов, splaysort может быть быстрее, чем O ( n log n ), показывая, что это адаптивный сорт . Чтобы выразить это количественно, пусть d x будет количеством позиций во входных данных, которые отделяют x от его предшественника, и пусть i x будет количеством элементов, которые появляются по одну сторону x во входных данных и по другую сторону x во входных данных. выход (количество инверсий , включающих x ). Тогда из динамической теоремы о пальцах для расширенных деревьев следует, что общее время расширенной сортировки ограничено
и по
- . [2]
Также можно показать, что Splaysort адаптивна к энтропии входной последовательности. [3]
Результаты эксперимента
[ редактировать ]В экспериментах Моффата, Эдди и Петерссона (1996) расширенная сортировка работала медленнее, чем быстрая сортировка в таблицах случайных чисел, в 1,5–2 раза и медленнее, чем сортировка слиянием, в меньшие времена. Для данных, состоящих из более крупных записей, опять же в случайном порядке, дополнительный объем перемещения данных, выполняемый быстрой сортировкой, значительно замедлял их по сравнению с алгоритмами на основе указателей, а время для расширенной сортировки и сортировки слиянием было очень близко друг к другу. Однако для почти предварительно отсортированных входных последовательностей (измеряемых количеством смежных монотонных подпоследовательностей в данных, количеством инверсий, количеством элементов, которые необходимо удалить, чтобы создать отсортированную подпоследовательность, или количеством несмежных монотонных подпоследовательностей на которые можно разделить входные данные) splaysort стал значительно более эффективным, чем другие алгоритмы. [1]
Элмасри и Хаммад (2005) сравнили splaysort с несколькими другими алгоритмами, которые адаптируются к общему количеству инверсий во входных данных, а также к быстрой сортировке. Они обнаружили, что для входных данных, у которых было достаточно мало инверсий, чтобы сделать адаптивный алгоритм быстрее, чем быстрая сортировка, расширенная сортировка была самым быстрым алгоритмом. [4]
Вариации
[ редактировать ]Сайкконен и Сойсилон-Сойнинен (2012) модифицируют splaysort, чтобы он был более адаптивным к количеству смежных монотонных подпоследовательностей во входных данных, и сообщают об экспериментах, показывающих, что полученный алгоритм работает быстрее на входных данных, которые почти предварительно отсортированы в соответствии с этой мерой. [5]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Моффат, Алистер; Эдди, Гэри; Петерссон, Ола (июль 1996 г.), «Splaysort: быстрая, универсальная, практичная», Software: Practice and Experience , 26 (7): 781–797, doi : 10.1002/(SICI)1097-024X(199607)26:7< 781::AID-SPE35>3.3.CO;2-2
- ^ Коул, Ричард (2000), «О гипотезе о динамическом пальце для расширенных деревьев. II. Доказательство», SIAM Journal on Computing , 30 (1): 44–85, CiteSeerX 10.1.1.36.2713 , doi : 10.1137/S009753979732699X , МР 1762706 .
- ^ Гэги, Трэвис (2005), Сортировка последовательности с низкой энтропией , arXiv : cs/0506027 , Bibcode : 2005cs........6027G .
- ^ Эльмасри, Амр; Хаммад, Абдельрахман (2005), «Эмпирическое исследование алгоритмов сортировки, чувствительных к инверсиям», Экспериментальные и эффективные алгоритмы: 4-й международный семинар, WEA 2005, остров Санторини, Греция, 10–13 мая 2005 г., Труды , конспекты лекций по информатике , том. 3503, Springer, стр. 597–601, номер документа : 10.1007/11427186_52 , ISBN. 978-3-540-25920-6 .
- ^ Сайкконен, Рику; Сойсалон-Сойнинен, Эльяс (2012), «Общий метод улучшения адаптивной сортировки на основе вставок», Алгоритмы и вычисления: 23-й международный симпозиум, ISAAC 2012, Тайбэй, Тайвань, 19–21 декабря 2012 г., Труды , Конспекты лекций по компьютеру Наука, том. 7676, Springer, стр. 217–226, номер doi : 10.1007/978-3-642-35261-4_25 , ISBN. 978-3-642-35260-7 .