Введение

Алгоритм сортировки

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

Обзор

Название алгоритма происходит от упрощенного варианта карточной игры «пасьянс». Игра начинается с перемешанной колоды карт. Карты раздаются по одной в последовательность стопок на столе, согласно следующим правилам. Изначально стопок нет. Первая разданная карта формирует новую стопку, состоящую из одной карты. Каждая последующая карта помещается на самую левую из существующих стопок, у которой верхняя карта имеет значение большее или равное значению новой карты, или справа от всех существующих стопок, тем самым образуя новую стопку. Когда больше не осталось карт для раздачи, игра заканчивается. Эта карточная игра преобразуется в двухфазный алгоритм сортировки следующим образом. Для заданного массива из n элементов из некоторой полностью упорядоченной области, рассматривайте этот массив как набор карт и смоделируйте игру сортировки пасьянсом. Когда игра завершится, восстановите отсортированную последовательность, последовательно выбирая минимальную видимую карту; иными словами, выполните k-путевое слияние p стопок, каждая из которых отсортирована внутри себя.

Анализ

Первая фаза сортировки терпением, симуляция карточной игры, может быть реализована таким образом, чтобы выполнять O(n log n) сравнений в худшем случае для входного массива из n элементов: будет не более n стопок, и по построению верхние карты стопок образуют возрастающую последовательность слева направо, поэтому нужную стопку можно найти с помощью бинарного поиска. Вторая фаза, объединение стопок, также может быть выполнена за время O(n) с использованием очереди с приоритетами. Если входные данные содержат естественные "последовательности", то есть неубывающие подмассивы, то производительность может быть значительно лучше. Фактически, если входной массив уже отсортирован, все значения образуют одну стопку, и обе фазы выполняются за время O(n). Сложность в среднем случае все равно остается O(n log n): любая равномерно случайная последовательность значений создаст ожидаемое количество стопок, на создание и объединение которых потребуется время O(n log n). Оценка практической производительности сортировки терпением приведена Чандрамули и Голдштейном, которые показали, что наивная реализация примерно в десять-двадцать раз медленнее, чем современная быстрая сортировка на их тестовом примере. Они объясняют это относительно небольшим количеством исследований, посвященных сортировке терпением, и разработали несколько оптимизаций, которые приближают ее производительность к быстрой сортировке в пределах двухкратного коэффициента. Если значения карт находятся в диапазоне от 1 до n, существует эффективная реализация с худшим временем выполнения для размещения карт в стопки, основанная на дереве Ван Эмде Боаса.

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

Сортировка терпения тесно связана с карточной игрой под названием "Игра Флойда". Эта игра очень похожа на игру, описанную ранее: первая разданная карта формирует новую стопку, состоящую из одной карты. Каждая последующая карта помещается либо на существующую стопку, верхняя карта которой имеет значение не меньше значения новой карты, либо справа от всех существующих стопок, тем самым формируя новую стопку. Когда больше нет карт для раздачи, игра заканчивается. Цель игры — закончить с как можно меньшим количеством стопок. Отличие от алгоритма сортировки терпения заключается в том, что нет требования помещать новую карту на самую левую стопку, куда это разрешено. Сортировка терпения представляет собой жадный подход к игре. Алдос и Диаконис предлагают считать выигрышным результатом получение 9 или менее стопок, что происходит с вероятностью примерно 5%.

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

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

Использование

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