Pull to refresh
0
Edison
Изобретаем успех: софт и стартапы

Пасьянсная сортировка

Reading time 4 min
Views 11K


В комментариях к предыдущим статьям изредка раздаются упрёки — зачем вообще изучать какие-либо другие сортировки, если уже есть самая быстрая в мире 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 и недавно сделала редизайн своего сайта
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+22
Comments 10
Comments Comments 10

Articles

Information

Website
www.edsd.ru
Registered
Founded
Employees
31–50 employees
Location
Россия