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

Терпеливая сортировка (англ. 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[/math] — количество стопок, на [math]p-i[/math]-ю позицию текущий элемент, перейти к предыдущему элементу по указателю.

Сложность

Создадим массив стеков для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем бинарный поиск. Соответственно, поиск самой левой стопки занимает [math]O(log[/math] [math]p)[/math], где p - количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает [math]O(n \cdot \log n)[/math]. Для получения отстортированного массива используем приоритетную очередь минимумов. На каждом шаге алгоритма необходимо извлечь из очереди стек с минимальной вершиной [math]O(1)[/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()

Пример

тест

Ссылки

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

Литература

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