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



    В комментариях к предыдущим статьям изредка раздаются упрёки — зачем вообще изучать какие-либо другие сортировки, если уже есть самая быстрая в мире 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 и недавно сделала редизайн своего сайта

    Edison

    329,00

    Изобретаем успех: софт и стартапы

    Поделиться публикацией

    Похожие публикации

    Комментарии 10
      +1
      Очень интересно. В виде кода, правда, не очень (с некоторым трудом могу представить практическое применение) — разве что один раз сравнить с другими и забыть (кстати, где количество операций для среднего и наихудшего случая?), а вот вживую с колодой надо будет попробовать…
        +1
        в худшем (когда карты в обратном порядке) кучек будет n, значит мы должны будем сравнивать каждую карту с каждой кучкой — получаем n^2 сравнений.
          +2
          мы должны будем сравнивать каждую карту с каждой кучкой

          Нет, кучки упорядочены, мы можем использовать бинарный поиск. Так что n*log(n)
            +2
            N кучек будет в случае прямого порядка, нет? В обратном кучка как раз будет одна.
              +1
              Почему? В случае обратно отсортированного массива будет одна кучка, т.е. один стек, из которого мы все значения и вытащим обратно (сравнивая каждое с одним другим значением). O(n).
              В случае отсортированного массива будет как раз n кучек, из каждой кучки мы добавим по одной карте в очередь, из которой мы вытащим все значения обратно (ни с чем не сравнивая). O(n)
              Не?
                +1
                Стеки прямо сортированные. Если встретили больше создаем новый.
                Получаем n стеков при обратной сортировке изначально.
                  +1
                  Видимо мы разные вещи называем прямым и обратным порядком. Для меня «обратно сортированный» == «отсортированный по убыванию».
                0
                В том то и дело, что реверс — это не худший случай, а лучший.

                В этом случае создастся всего одна стопка (напомню, что стопки всегда обратно упорядочены).
              +1
              nlogn для массива изначально отсортированного в обратном порядке.
              И n дополнительной памяти. При этом ее надо выделять очень хитро. Одним куском не выделить. Чую там накладных расходов море будет.

              Зачем? Есть же mergesort и quicksort. Один гарантирует nlogn при n памяти выделенной одним куском, второй nlogn при минимальном везении и in place работает.

              А для колоды и прочих таких случаев bucket sort. Его не обойти.
                +1
                от 30 до 39 (да, конечно, внутри масти количество карт не равно ровно десяти, но вы поняли, что имеется ввиду).
                от 30 до 3F 3D

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое