Терпеливая сортировка
Терпеливая сортировка (англ. patience sorting) - алгоритм сортировки с худшей сложностью . Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. Алгоритм назван по одному из названий карточной игры "Солитёр" — "Patience".
Алгоритм
Имеем массив , элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия — новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа от уже имеющихся и сделаем её вершиной наш элемент. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая. Для получения отсортированного массива выполним шагов: на -м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив на -ю позицию. Длина наибольшей возрастающей подпоследовательности равна количеству стопок. Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить шагов, начав с вершины самой правой стопки: на -м шаге записать в на -ю позицию текущий элемент, перейти к предыдущему элементу по указателю, — количество стопок.
Сложность
Создадим массив стеков для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем бинарный поиск. Соответственно, поиск самой левой стопки занимает , где p - количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает . Для получения отстортированного массива используем бинарную кучу. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за , где p - количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за . Получение отсортированного массива займёт времени. Получение наибольшей возрастающей подпоследовательности выполняется за по описанному выше алгоритму. Таким образом, алгоритм сортировки требует времени в худшем случае и дополнительной памяти при любом раскладе. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма сортировки составляет . Такая оценка основывается на структуре данных Дерево ван Эмде Боаса.
Псевдокод
//формирование стопок
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()
Пример
Рассмотрим работу алгоритма на последовательности: .
Формирование стопок:
| Стопка 1 | Стопка 2 | Стопка 3 | Стопка 4 | Стопка 5 | Стопка 6 |
|---|---|---|---|---|---|
| 3 | не существует | не существует | не существует | не существует | не существует |
| 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
