In the comments to the previous articles, occasionally there are reproaches - why bother to study any other sorting at all if there is already the fastest Quick sort in the world. Mol-de, all this pretentious exotic has no use and no one needs.


Percy Diaconis , who has studied solitaire sorting along and across, believes that it is the fastest way to manually organize a deck of cards.

So, if a respected mathematician (and an experienced card magician) does not lie, then the practical value of the algorithm is all right.

And now watch your hands.

Stage 1. Spoon in stacks.

So, take the worms from the deck. They will represent an array of thirteen random elements.



We need to decompose the cards in several piles so that in each pile the cards are an ordered sequence.

In other words, our task at this stage is to quickly create several ordered sub-arrays from an existing unsorted array. At the same time, it is highly desirable that the number of these subarrays be smaller, which means that we must strive to ensure that the subarrays are more authentic. This is done as follows.

The first card is the start of the first pile.



In this pile, we shift the cards one by one, until the next card being transferred is smaller than the top one in the pile.

In addition, each stack is a stack - we do not work with the whole stack, but only with the top card in it, which we put last.



If the current card is more than the minimum card in the pile, then you will have to create a new handful, the current card opens a new pile.



Stack sequence is important! If their number is already more than one, then we place the next card not in the last pile, but in the leftmost pile in which we can put.

Right now, after the lady, you need to attach a nine somewhere. Mechanically, I want to put the card in the second pile, but in the first pile the top card is greater than nine. So, we can continue the first pile, without violating its orderliness. The next three, which comes after the nine, is also incidentally sent to the first pile.



Seven and six cannot be added to the first pile (they are larger than the top card in it), but they still have a place in the second pile.



Ace starts a new stack. The remaining fines fall into different trays, depending on how far to the left was the stack, where you could insert.



As a result, the cards are spread out in several piles. In each pile of cards are a decreasing sequence, at the top - the smallest card. Stacks are stacks.

Since we tried first to fill those piles that were to the left, we have the smallest possible quantity. If we just walked through the array and extracted diminishing subarrays from it, then heaps, naturally, will get much more.

Stage 2. Bottom row

Shift the available top cards down a bit so that they stand in a separate row. If the stacks are stacks, then we will work with the bottom row as with a queue.



What is important - the available top cards in the stacks are also an ordered sequence. The bottom row is already sorted in ascending order. No wonder - when forming stacks of cards, smaller ones were sent as far as possible to the left.

In the future, until the end of the sorting, we are not interested in all the cards that are laid out on the table. Only these are needed:

• The leftmost card (let's call it current) in the bottom row queue.
• In stacks of stacks we work only with the top available cards. In this case, only those piles that are directly on the current map and to the left are needed. Stacks that are to the right at this moment are not needed.

In the bottom row we go over cards from left to right cards. The left most is the current minimum, we return it to the original top row. At the same time, each time we return another card to the base, it is necessary to put another one in its place. Where to get it from? From those stacks that are above the current card and to the left of it - among the available cards, the minimum is selected, which moves to the vacant position of the current left card in the bottom row, and from there to the main array.

Two in the array is returned immediately. The vacant space is occupied by a triple (we move it from the first stack to the lower row), and from the lower row the triple, as the current minimum, goes to the main array. In the first two piles, the minimum is searched again - this is the four - which also goes home. The current minimum is five, etc.



By combining work with an ordered queue in ascending order and stacks arranged in descending order, we very quickly get all the elements from minimum to maximum. Something like that, in general.

Animation of this process.



If all of the above translate into Python, then you get this:

from functools import total_ordering
from bisect import bisect_left
from heapq import merge
@total_orderingclassPile(list):def__lt__(self, other):return self[-1] < other[-1]
    def__eq__(self, other):return self[-1] == other[-1]
defpatience_sort(n):
    piles = []
    # sort into pilesfor 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])

Links

Patience sorting ( Google-translate )

Patience sorting source (s )

: Princeton CS: Listing the

most common screenings ( Google-translate )

Wiki notes: patient sorting

Word Aligned ( Google-translate )

Articles series:

• Excel application AlgoLab.xlsm
• Exchange sorting
• Sorting inserts
  • Librarian sort
  • Solitaire sorting
  • Sort "Tower of Hanoi"
  • Sort by Young table
  • Inversion Sort
  • Comparing sorting inserts
• Sort by selection
• Merge sort

In the AlgoLab application, this sorting is now active. At the same time, visualization is possible in two modes: in the form of maps (the default mode) and simply in the form of numbers. However, for the card style, it is necessary that the difference between the maximum and minimum elements in the array be less than 54 (the number of cards in the deck, including two jokers). If this condition is not fulfilled or the card mode is turned off altogether (for this, card = 0 must be entered in the comment to the cell with the sort name), then the visualization will be in the form of dull digits.



Suits are considered in order of preference seniority: peaks <clubs <diamonds <hearts.

That is, any diamonds suit card is more than any club suit card, any heart suit card is greater than any peak suit card, etc. If we draw an analogy with numbers, the peaks are from 0 to 9, clubs are from 10 to 19, diamonds are from 20 to 29, hearts are from 30 to 39 (yes, of course, inside the suit the number of cards is not exactly ten, but you understand what I mean). As for the seniority inside the suit , it will be normal: from two to ace. You can even take jokers that are older than all the other cards. At the same time, the red joker is more powerful than black.

The article was written with the support of the EDISON Software company, which is professionally engaged in web development and has recently redesigned its website.