Сортировка терпения

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

Обзор

Название алгоритма происходит от упрощенного варианта карточной игры в терпение. Игра начинается с перетасованной колоды карт. Карты раздаются по одной в последовательность стопок на столе в соответствии со следующими правилами. ^[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] дают описание эффективной реализации алгоритма, не несущей дополнительных асимптотических затрат по сравнению с сортировкой (поскольку хранение, создание и обход обратных указателей требуют линейного времени и пространства). Далее они показывают, как сообщить обо всех самых длинных возрастающих подпоследовательностях из одних и тех же результирующих структур данных .

История

Сортировка по терпению была названа К. Л. Маллоузом, который приписал свое изобретение компании ASC Ross в начале 1960-х годов. ^[1] Согласно Олдосу и Диаконису, ^[4] сортировка по терпению была впервые признана Хаммерсли как алгоритм вычисления наибольшей возрастающей длины подпоследовательности. ^[5] ASC Ross и независимо Роберт В. Флойд признали его алгоритмом сортировки. Первоначальный анализ был проведен Маллоузом. ^[6] Игра Флойда была разработана Флойдом в переписке с Дональдом Кнутом . ^[2]

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

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