Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Сортировка терпения
Учебный классАлгоритм сортировки
Структура данныхМножество
Наихудшая производительностьO ( п войти п )
Лучшая производительностьО ( п ) ; происходит, когда ввод предварительно отсортирован [1]

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

Обзор [ править ]

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

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

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

Анализ [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

История [ править ]

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

Используйте [ редактировать ]

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

Ссылки [ править ]

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