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

Patience sorting
Сортировка терпения
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакльО(п бревно п)
Лучший случай спектакльО(п); происходит, когда вход предварительно отсортированный[1]

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

Обзор

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

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

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

Анализ

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

Когда входные данные содержат естественные "прогоны", то есть неубывающие подмассивы, производительность может быть значительно лучше. Фактически, когда входной массив уже отсортирован, все значения образуют одну стопку, и обе фазы выполняются в О(п) время. В средний случай сложность все еще О(п бревно п): любая равномерно случайная последовательность значений даст ожидаемое число из О(√п) геморрой,[3] которые принимают О(п бревно √п) = О(п бревно п) время производить и объединять.[1]

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

Если значения карт находятся в диапазоне 1, . . . , п, есть эффективная реализация с О(п бревно п) худший случай время складывания карт в стопки, полагаясь на Дерево Ван Эмде Боаса.[3]

Отношение к другим проблемам

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

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

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

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

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

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

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

История

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

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

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

Рекомендации

  1. ^ а б c d е ж Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение - это добродетель: пересмотр слияния и сортировки на современных процессорах (PDF). SIGMOD / PODS.
  2. ^ а б c Бурштейн, Александр; Лэнкхэм, Исайя (2006). «Комбинаторика терпения сортировки стопок» (PDF). Séminaire Lotharingien de Combinatoire. 54A. arXiv:математика / 0506358. Bibcode:2005математика ...... 6358B.
  3. ^ а б c Беспамятных, Сергей; Сигал, Майкл (2000). «Перечисление самых длинных возрастающих подпоследовательностей и сортировка терпения». Письма об обработке информации. 76 (1–2): 7–11. CiteSeerX 10.1.1.40.5912. Дои:10.1016 / s0020-0190 (00) 00124-1.
  4. ^ а б Олдос, Дэвид; Диаконис, Перси (1999). «Самые длинные возрастающие подпоследовательности: от сортировки по терпению до теоремы Байка-Дейфта-Йоханссона». Бюллетень Американского математического общества. Новая серия. 36 (4): 413–432. Дои:10.1090 / s0273-0979-99-00796-x.
  5. ^ Хаммерсли, Джон (1972). Несколько саженцев исследования. Proc. Шестой симпозиум Беркли. Математика. Статист. и вероятность. 1. Калифорнийский университет Press. С. 345–394.
  6. ^ Мэллоуз, К. Л. (1973). «Сортировка терпения». Бык. Inst. Математика. Приложение. 9: 216–224.
  7. ^ Касс, Стив (30 апреля 2002 г.). "Статистическое управление процессами". SQL Server Pro. Получено 23 апреля 2014.