Терпеливая сортировка — различия между версиями
(→Псевдокод) |
(→Псевдокод) |
||
| Строка 8: | Строка 8: | ||
== Псевдокод == | == Псевдокод == | ||
| − | //формирование стопок | + | //формирование стопок |
| − | + | List<Stack<E>> piles | |
| − | List<Stack<E>> piles | + | '''for''' (i = 0..n - 1) |
| − | '''for''' (i = 0..n-1) | ||
Stack<E> pile = Pile(source[i]) | Stack<E> pile = Pile(source[i]) | ||
i = BinarySearch(piles, pile) | i = BinarySearch(piles, pile) | ||
| − | '''if''' (i==piles.size) | + | '''if''' (i == piles.size) |
piles.Add(pile) | piles.Add(pile) | ||
'''else''' | '''else''' | ||
piles[i].Add(Pile(source[i])) | piles[i].Add(Pile(source[i])) | ||
| − | piles[ | + | piles[i].Top.Previous() = piles[i - 1].Top // для последующего получения НВП |
//Получение отсортированного массива | //Получение отсортированного массива | ||
| − | |||
bool comparePiles (Stack<E> x, Stack<E> y) | bool comparePiles (Stack<E> x, Stack<E> y) | ||
| − | return x.Peek()<y.Peek() | + | return x.Peek() < y.Peek() |
| − | |||
PriorityQueue<Stack<E>> q(piles, comparePiles) | PriorityQueue<Stack<E>> q(piles, comparePiles) | ||
| − | + | '''for'''(i = 0..n - 1) | |
| − | '''for'''(i=0..n-1) | + | answer[i] = q.Min().Pop() |
| − | answer[i]=q.Min().Pop() | ||
//Получение наибольшей возрастающей подпоследовательности | //Получение наибольшей возрастающей подпоследовательности | ||
| − | + | answer[n - 1] = piles[piles.size - 1].Top | |
| − | answer[n-1]=piles[piles.size-1].Top | + | E prev = answer[n - 1].Previous() |
| − | E prev = answer[n-1].Previous | + | '''for'''(i = n - 2..0) |
| − | '''for'''(i=n-2..0) | ||
answer[i]=prev | answer[i]=prev | ||
| − | prev = answer[i].Previous | + | prev = answer[i].Previous() |
== Пример == | == Пример == | ||
Версия 02:31, 7 июня 2014
Терпеливая сортировка (англ. patience sorting) - алгоритм сортировки с худшей сложностью . Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. Алгоритм назван по одному из названий карточной игры "Солитёр" — "Patience".
Содержание
Алгоритм
Имеем массив , элементы которого нужно отсортировать по возрастанию. Разложим элементы массива по стопкам: для того чтобы положить элемент в стопку, требуется выполнение условия — новый элемент меньше элемента, лежащего на вершине стопки; либо создадим новую стопку справа от уже имеющихся и сделаем её вершиной наш элемент. Используем жадную стратегию: каждый элемент кладётся в самую левую стопку из возможных, если же таковой нет, справа от существующих стопок создаётся новая. Для получения отсортированного массива выполним шагов: на -м шаге выберем из всех вершин стопок наименьшую, извлечём её и запишем в массив на -ю позицию. Длина наибольшей возрастающей подпоследовательности равна количеству стопок. Для получения наибольшей возрастающей подпоследовательности при формировании стопок проведём следующие операции: каждый раз, положив элемент на вершину стопки, будем создавать указатель на возможный предыдущий элемент (вершину ближайшей слева стопки). В конце для получения наибольшей возрастающей подпоследовательности нужно выполнить шагов, начав с вершины самой правой стопки: на -м шаге записать в ,где — количество стопок, на -ю позицию текущий элемент, перейти к предыдущему элементу по указателю.
Псевдокод
//формирование стопок
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
