В комментариях к предыдущим статьям изредка раздаются упрёки — зачем вообще изучать какие-либо другие сортировки, если уже есть самая быстрая в мире Quick sort. Мол-де, вся эта вычурная экзотика не имеет применения и никому не нужна.


Перси Дьяконис, вдоль и поперёк изучивший пасьянсную сортировку, считает, что она является быстрейшим способом ручного упорядочивания колоды карт.

Так что, если уважаемый математик (и бывалый карточный фокусник) не врёт, то с практической ценностью алгоритма всё в порядке.

А теперь следите за руками.

Этап 1. Раскладываем по стопкам



Итак, возьмём из колоды черви. Они будут изображать массив из тринадцати случайных элементов.



Нам нужно разложить карты в несколько стопок, таким образом, чтобы в каждой стопке карты представляли из себя упорядоченную последовательность.

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

Первая карта — начало первой стопки.



В эту стопку перекладыв��ем карты по очереди, до тех пор, пока очередная перекладываемая карта меньше чем верхняя в стопке.

При этом каждая стопка является стеком — мы работаем не со всей стопкой, а только с верхней картой в ней, которую положили последней.



Если текущая карта больше чем минимальная в стопке, значит, придётся создавать новую кучку, текущая карта открывает новую стопку.



Очерёдность стопок важна! Если их количество уже более одного, то очередную карту мы кладём не в последнюю стопку, а в самую левую стопку, в которую можем положить.

Вот сейчас после дамы надо куда-то пристроить девятку. Механически хочется положить карту во вторую стопку, но в первой стопке верхняя карта больше девятки. Значит, можем продолжить первую стопку, не нарушив её упорядоченность. Следующую тройку, которая идёт следом за девяткой, тоже кстати, отправляется в первую стопку.



Семёрку и шестёрку в первую стопку добавить нельзя (они больше верхней карты в ней), но во второй стопке им пока находится место.



Туз начинает новую стопку. Оставшаяся мелочь попадает в разные лотки, в зависимости от того, насколько левее была стопка, куда можно было вставить.



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

Так как мы старались сначала заполнять те стопки, что находились левее, у нас образовалось наименьшее возможно количество. Если бы мы просто прошлись по массиву и выделяли из него убывающие подмассивы, то кучек, естественно будет полчаться намного больше.



Этап 2. Нижний ряд



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



Что немаловажно — доступные верхние карты в стопках также представляют из себя упорядоченную последовательность. Нижний ряд уже отсортирован по возрастанию. Что и немудрено — при формировании стопок карты поменьше отправлялись как можно левее.

В дальнейшем до конца сортировки нас интересуют не все карты из тех что разложены на столе. Нужны только вот эти:

  • Самая левая карта (назовём её — текущая) в нижнем ряду-очереди.
  • В стопках-стеках работаем только с верхними доступными картами. При этом нужны только те стопки, которые находятся непосредственно на текущей картой и левее. Стопки которые находятся правее в этот момент не нужны.


В нижнем ряду перебираем карты слева-направо карты. Самая лева — текущий минимум, его возвращаем в первоначальный верхний ряд. При этом каждый раз, когда мы вернули на базу очередную карту, необходимо на её место положить другую. Откуда её взять? Из тех стопок что находятся над тек��щей картой и левее её — среди доступных карт выбирается минимум, который перемещается на вакантное место текущей левой карты в нижнем ряду, а оттуда — в основной массив.

Двойка в массив возвращается сразу. Освободившееся место занимает тройка (перемещаем её из первой стопки в нижний ряд), а из нижнего ряда тройка как текущий минимум уходит в основной массив. В первых двух стопках ищется снова минимум — это четвёрка — которая тоже отправляется домой. Текущим минимумом становится пятёрка и т.д.



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

Анимация данного процесса.



Если всё вышеуказанное перевести на Python, то получится вот это:

from functools import total_ordering
from bisect import bisect_left
from heapq import merge
 
@total_ordering
class Pile(list):
    def __lt__(self, other): return self[-1] < other[-1]
    def __eq__(self, other): return self[-1] == other[-1]
 
def patience_sort(n):
    piles = []
    # sort into piles
    for x in n:
        new_pile = Pile([x])
        i = bisect_left(piles, new_pile)
        if i != len(piles):
            piles[i].append(x)
        else:
            piles.append(new_pile)
 
    # use a heap-based merge to merge piles efficiently
    n[:] = merge(*[reversed(pile) for pile in piles])


Ссылки


Patience sorting (Google-translate)

Patience sorting source

Princeton CS: Longest increasing subsequence

Combinatorics of patience sorting piles (Google-translate)

Вики-конспекты: терпеливая сортировка

Word Aligned (Google-translate)

Статьи серии:




В приложении AlgoLab эта сортировка теперь активна. При этом визуализация возможна в двух режимах: в виде карт (режим по умолчанию) и просто в виде чисел. Однако для карточного стиля нужно чтобы разница между максимальным и минимальным элементом в массиве была меньше чем 54 (количество карт в колоде, включая два джокера). Если это условие не выполняется или же карточный режим вовсе выключен (для этого в комментарии к ячейке с названием сортировки нужно прописать card=0), то визуализация будет в виде унылых цифр.

Масти рассматриваются в порядке преферансного старшинства: пики < трефы < бубны < червы.


То есть любая карта бубновой масти бубна больше любой карты трефовой масти, любая карта червовой масти больше любой карты пиковой масти и т.п. Если провести аналогию с числами, то пики — это от 0 до 9, трефы — от 10 до 19, бубны — от 20 до 29, червы — от 30 до 39 (да, конечно, внутри масти количество карт не равно ровно десяти, но вы поняли, что имеется ввиду). Что касается старшинства внутри масти, то оно будет обычное: от двойки до туза. Можно ещё взять джокеров, которые старше всех остальных карт. При этом красный джокер весомее чёрного.

EDISON Software - web-development
Статья написана при поддержке компании EDISON Software, которая профессионально занимается разработкой для web и недавно сделала редизайн своего сайта