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

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

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	О ( п журнал п )
Лучшая производительность	На ) ​ ​ ; происходит, когда ввод предварительно отсортирован
Оптимальный	?

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

Обзор

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

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

S. Bespamyatnikh and M. Segal дать описание эффективной реализации алгоритма, не требующей дополнительных асимптотических затрат по сравнению с сортировкой (поскольку хранение, создание и обход обратных указателей требуют линейного времени и пространства). Далее они показывают, как сообщить обо всех самых длинных возрастающих подпоследовательностях из одних и тех же результирующих структур данных .

История

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

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

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