Терпение сортировка

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

Обзор

Название алгоритма происходит от упрощенного варианта карточной игры «Пассив». Игра начинается с перетасованной колоды карт. Карты раздаются по одной в последовательность стопок на столе, согласно следующим правилам. ^[2]

Изначально стопок нет. Первая сданная карта формирует новую стопку, состоящую из одной карты.
Каждая последующая карта кладется в самую левую существующую стопку, верхняя карта которой имеет значение больше или равное значению новой карты, или справа от всех существующих стопок, таким образом образуя новую стопку.
Когда не остается больше карт для раздачи, игра заканчивается.

Эта карточная игра превращается в двухфазный алгоритм сортировки следующим образом. Учитывая массив из $n$ элементов из некоторого полностью упорядоченного домена, рассмотрим этот массив как коллекцию карт и смоделируем игру сортировки пасьянса. Когда игра закончится, восстановите отсортированную последовательность, многократно выбирая минимальную видимую карту; другими словами, выполните $k$ -стороннее слияние $p$ стопок , каждая из которых внутренне отсортирована.

Анализ

Первая фаза сортировки по принципу терпения, симуляция карточной игры, может быть реализована для выполнения $O (n log n)$ сравнений в худшем случае для $n$ -элементного входного массива: будет не более $n$ стопок, и по построению верхние карты стопок образуют возрастающую последовательность слева направо, поэтому нужную стопку можно найти с помощью бинарного поиска . ^[1] Вторая фаза, объединение стопок, может быть выполнена во времени, а также с использованием приоритетной очереди . ^[1] $O(n\log n)$

Когда входные данные содержат естественные «прогоны», т. е. неубывающие подмассивы, то производительность может быть строго лучше. Фактически, когда входной массив уже отсортирован, все значения образуют одну кучу, и обе фазы выполняются за время $O (n)$ . Средняя сложность по-прежнему составляет $O (n log n)$ : любая равномерно случайная последовательность значений даст ожидаемое количество куч , ^[3] для создания и объединения которых требуется время. ^[1] $O({\sqrt {n}})$ $O(n\log {\sqrt {n}})=O(n\log n)$

Оценка практической производительности сортировки с терпением дана Чандрамули и Голдштейном, которые показывают, что наивная версия примерно в десять-двадцать раз медленнее, чем современная быстрая сортировка на их контрольной задаче. Они связывают это с относительно небольшим объемом исследований, вложенных в сортировку с терпением, и разрабатывают несколько оптимизаций, которые доводят ее производительность до двухкратного показателя быстрой сортировки. ^[1]

Если значения карт находятся в диапазоне $1, . . . , n$ , то существует эффективная реализация с наихудшим временем выполнения для размещения карт в стопках, основанная на дереве Ван Эмде Боаса . ^[3] $O(n\log n)$

Связь с другими проблемами

Сортировка терпения тесно связана с карточной игрой под названием «игра Флойда». Эта игра очень похожа на игру, набросанную ранее: ^[2]

Первая сданная карта формирует новую стопку, состоящую из одной карты.
Каждая последующая карта кладется в какую-либо существующую стопку, верхняя карта которой имеет значение не меньше значения новой карты, или справа от всех существующих стопок, образуя таким образом новую стопку.
Когда не остается больше карт для раздачи, игра заканчивается.

Цель игры — закончить игру с как можно меньшим количеством стопок. Отличие от алгоритма сортировки «Пасьянс» в том, что нет необходимости класть новую карту в самую левую стопку, где это разрешено. Сортировка «Пасьянс» представляет собой жадную стратегию для игры в эту игру.

Олдос и Диаконис предлагают определить 9 или менее стопок как выигрышный результат для $n = 52$ , что происходит с вероятностью приблизительно 5%. ^[4]

Алгоритм нахождения самой длинной возрастающей подпоследовательности

Сначала выполните алгоритм сортировки, как описано выше. Количество стопок — это длина самой длинной подпоследовательности. Всякий раз, когда карта помещается наверх стопки, поместите обратный указатель на верхнюю карту в предыдущей стопке (которая, по предположению, имеет меньшее значение, чем новая карта). В конце проследите за обратными указателями от верхней карты в последней стопке, чтобы восстановить убывающую подпоследовательность самой длинной длины; ее обратная последовательность является ответом на алгоритм самой длинной возрастающей подпоследовательности.

С. Беспамятных и М. Сегал ^[3] дают описание эффективной реализации алгоритма, не требующей дополнительных асимптотических затрат по сравнению с сортировкой (поскольку хранение, создание и обход обратных указателей требуют линейного времени и пространства). Они также показывают, как сообщать все самые длинные возрастающие подпоследовательности из тех же результирующих структур данных .

История

Сортировка терпения была названа CL Mallows, который приписал ее изобретение ASC Ross в начале 1960-х годов. ^[1] Согласно Aldous и Diaconis, ^[4] сортировка терпения была впервые признана как алгоритм для вычисления самой длинной увеличивающейся длины подпоследовательности Hammersley. ^[5] ASC Ross и независимо Robert W. Floyd признали ее как алгоритм сортировки. Первоначальный анализ был проведен Mallows. ^[6] Игра Floyd была разработана Floyd в переписке с Donald Knuth . ^[2]

Использовать

Алгоритм сортировки «терпеливости» может быть применен к управлению процессами . В серии измерений существование длинной возрастающей подпоследовательности может использоваться в качестве маркера тренда. Статья 2002 года в журнале SQL Server включает реализацию SQL в этом контексте алгоритма сортировки «терпеливости» для длины самой длинной возрастающей подпоследовательности. ^[7]

Ссылки

^ abcdef Чандрамули, Бадриш; Голдштейн, Джонатан (2014). Терпение — добродетель: пересмотр слияния и сортировки на современных процессорах (PDF) . SIGMOD/PODS.
^ abc Бурштейн, Александр; Ланкхэм, Исайя (2006). "Комбинаторика терпения сортировки куч" (PDF) . Лотарингский семинар по комбинаторике . 54A . arXiv : math/0506358 . Bibcode :2005math......6358B.
^ abc Беспамятных, Сергей; Сегал, Майкл (2000). «Перечисление наиболее длинных возрастающих подпоследовательностей и терпеливая сортировка». Information Processing Letters . 76 (1–2): 7–11. CiteSeerX 10.1.1.40.5912 . doi :10.1016/s0020-0190(00)00124-1.
^ ab Aldous, David ; Diaconis, Persi (1999). "Самые длинные возрастающие подпоследовательности: от сортировки с терпением до теоремы Бейка-Дейфта-Йоханссона". Бюллетень Американского математического общества . Новая серия. 36 (4): 413–432. doi : 10.1090/s0273-0979-99-00796-x .
^ Хаммерсли, Джон (1972). Несколько ростков исследований . Труды Шестой симпозиум Беркли по математике, статистике и вероятности. Т. 1. Издательство Калифорнийского университета. С. 345–394.
^ Mallows, CL (1973). «Сортировка терпения». Bull. Inst. Math. Appl . 9 : 216–224.
^ Касс, Стив (30 апреля 2002 г.). «Статистическое управление процессами». SQL Server Pro . Получено 23 апреля 2014 г.

Реализация алгоритма Wikibook имеет страницу на тему: Сортировка терпения