Терпеливая сортировка

Терпеливая сортировка (англ. patience sorting) - алгоритм сортировки с худшей сложностью [math]O(n[/math] [math]log[/math] [math]n)[/math]. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. Алгоритм назван по одному из названий карточной игры "Солитёр" — "Patience".

Алгоритм

Имеем массив [math]source [0..n][/math], элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия — новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа от уже имеющихся и сделаем её вершиной наш элемент. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая. Для получения отсортированного массива выполним [math]n[/math] шагов: на [math]i[/math]-м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив [math]ans [0..n][/math] на [math]i-1[/math]-ю позицию. Длина наибольшей возрастающей подпоследовательности равна количеству стопок. Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить [math]p[/math] шагов, начав с вершины самой правой стопки: на [math]i[/math]-м шаге записать в [math]lis[0..p-1][/math] на [math]p-i[/math]-ю позицию текущий элемент, перейти к предыдущему элементу по указателю, [math]p[/math] — количество стопок.

Сложность

Создадим массив стеков для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем бинарный поиск. Соответственно, поиск самой левой стопки занимает [math]O(log[/math] [math]p)[/math], где p - количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает [math]O(n \cdot \log n)[/math]. Для получения отстортированного массива используем бинарную кучу. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за [math]O(log[/math] [math]p)[/math], где p - количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за [math]O(log[/math] [math]p)[/math]. Получение отсортированного массива займёт [math]O(n \cdot log[/math] [math]n)[/math] времени. Получение наибольшей возрастающей подпоследовательности выполняется за [math]O(n)[/math] по описанному выше алгоритму. Таким образом, алгоритм сортировки требует [math]O(n \cdot \log n)[/math] времени в худшем случае и [math]O(n)[/math] дополнительной памяти при любом раскладе. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма сортировки составляет [math]O(n \cdot \log \log n)[/math]. Такая оценка основывается на структуре данных Дерево ван Эмде Боаса.

Псевдокод

  //формирование стопок
  List<Stack<E>> piles
  for (i = 0..n - 1)
  Stack<E> pile = Pile(source[i])
  i = BinarySearch(piles, pile)
  if (i == piles.size)
      piles.Add(pile)
  else
      piles[i].Add(Pile(source[i]))
  piles[i].Top.Previous() = piles[i - 1].Top // для последующего получения НВП

  //Получение отсортированного массива
  bool comparePiles (Stack<E> x, Stack<E> y)
     return x.Peek() < y.Peek()
  PriorityQueue<Stack<E>> q(piles, comparePiles)
  for (i = 0..n - 1)
     answer[i] = q.Min().Pop()

  //Получение наибольшей возрастающей подпоследовательности
  answer[n - 1] = piles[piles.size - 1].Top
  E prev = answer[n - 1].Previous()
  for (i = n - 2..0)
     answer[i]=prev
     prev = answer[i].Previous()

Пример

Рассмотрим работу алгоритма на последовательности: [math]3 1 2 4 5 0[/math].

Формирование стопок:

Стопка 1	Стопка 2	Стопка 3	Стопка 4	Стопка 5	Стопка 6
3 1	не существует	не существует	не существует	не существует	не существует
3 1	2 (предшествующий элемент - 1)	не существует	не существует	не существует	не существует
3 1	2	4 (предшествующий элемент - 2)	не существует	не существует	не существует
3 1	2	4	5 (предшествующий элемент - 4)	не существует	не существует
3 1 0	2	4	5	не существует	не существует

Получим отсортированный массив:

Вершины	Минимум
0 2 4 5	0
1 2 4 5	1
3 2 4 5	2
3 4 5	3
4 5	4
5	5

Получим наибольшую возрастающую подпоследовательность:

Текущий элемент	Предшествующий
5	4
4	2
2	1
1	null

Ссылки

• Терпеливая сортировка в английской Википедии
• Наглядное описание алгоритма на английском языке

Литература

• Sergei Bespamyatnikh and Michael Segal Pacific Inst. for the Math. Sci. Preprints, PIMS-99-3., pp.7–8