Introduction
Patience sort is one of the common sorting algorithms. This algorithm is inspired and named by the card game called Solitaire. An another variant of this algorithm is used to find the longest increasing subsequence in a given array, which is said to used in SQL Server, process control.
Little bit history from the below reference paper from David Aldous and Persi Diaconis, Patience sort was named by C.L. Mallows in early 1960's but was never published.
Time Complexity: O(N2)
Time Complexity using priority queue: O(N * log(N)) [Example is given below]
Auxiliary Space: O(N) [Auxiliary space means extra or temporary space used by the algorithm to process the logic]
Algorithm
- Rules
- Number can be added to the pile only if it is lesser than current number/card.
- If the existing piles does't meet the first rule, a new pile is created.
- Ideally the goal is to have list of lists holding sorted values, possibly lesser number of piles.
- Logic
- Involves two steps process, creation and merging of piles.
- Piles
- Initialize an empty 2D list with no piles.
- Loop through each number/card.
- First card forms a new pile consisting single number/card.
- Each subsequent card is placed in the leftmost (top) of the existing pile if the value is greater or equal to new number/card value.
- If the above rule fails, when it is unable to find greater element in any of the top values in the available piles, a new pile is created by adding the number/card on the top of the stack.
- Merge
- Given sorted arrays perform merge in k-way merge operation using priority queue (min-heap). As we would want to find the smallest element and followed by the next smallest. Let's say to find any element from the list this algorithm would not be suitable.
- Priority queue, is kind of queue data structure which additionally holds priority value for every element. There are different ways the priority could be defined. Such as :
- The largest element holds higher priority
- The smallest element holds higher priority
- In python we have predefined module available perform this operation, "heapq".
Visualization
 |
| Credits: https://assets.leetcode.com/users/images/4eb9f4c5-5612-4761-8da1-9f5e58e5d9ae_1616834711.464945.png |
Source Code
import bisect
import heapq
def patience_sort(seq):
# array of piles initially null
piles = []
print("Started with the given input of array values ", seq, "\n")
# Each subsequent card is placed on the leftmost existing pile
# whose top card has a value greater than or
# equal to the new card's value,
# or to the right of all of the existing piles,
# thus forming a new pile.
print("Lets create a list of piles using bisect algorithm:")
for x in seq:
new_pile = [x]
# Bisect algorithm is to find a position in list where an element
# needs to be inserted to keep the list in sorted order.
# If the element is already present in the list,
# the left most position where element has to be inserted is returned.
i = bisect.bisect_left(piles, new_pile)
if i != len(piles):
piles[i].insert(0, x)
else:
piles.append(new_pile)
print("At each level status of piles {}".format(piles))
print("List of increasing subsequences are ", piles, "\n")
print("Lets perform the sorting operation for the piles:")
print("Before sort status for sequence {}, having piles {}".format(seq, piles))
# priority queue allows us to retrieve least pile efficiently
for i in range(len(seq)):
small_pile = piles[0]
seq[i] = small_pile.pop(0)
# Heap data structure is mainly used to represent a priority queue.
# Here the smallest heap element is given higher priority.
# Implements as complete binary tree.
# For each elements are pushed or popped, heap structure is maintained.
if small_pile:
# Here the function inserts and pops elements in one statement.
# In this, the element is first popped, then the element is pushed.
# heapreplace() is equivalent to heappop() followed by heappush().
# The order will be adjusted, so the heap structure is maintained.
heapq.heapreplace(piles, small_pile)
else:
# This function is used to remove and return the smallest element from the heap.
# The order is adjusted, so that heap structure is maintained.
heapq.heappop(piles)
print("At level {} status for sequence {}, having piles {}".format(i, seq, piles))
print("\nFinally! After patience sort input array is sorted ", seq)
assert not piles
input_values = [3, 7, 5, 6, 4, 2, 10, 9, 8]
patience_sort(input_values)
Output
Started with the given input of array values [3, 7, 5, 6, 4, 2, 10, 9, 8]
Lets create a list of piles using bisect algorithm:
At each level status of piles [[3]]
At each level status of piles [[3], [7]]
At each level status of piles [[3], [5, 7]]
At each level status of piles [[3], [5, 7], [6]]
At each level status of piles [[3], [4, 5, 7], [6]]
At each level status of piles [[2, 3], [4, 5, 7], [6]]
At each level status of piles [[2, 3], [4, 5, 7], [6], [10]]
At each level status of piles [[2, 3], [4, 5, 7], [6], [9, 10]]
At each level status of piles [[2, 3], [4, 5, 7], [6], [8, 9, 10]]
List of increasing subsequences are [[2, 3], [4, 5, 7], [6], [8, 9, 10]]
Lets perform the sorting operation for the piles:
Before sort status for sequence [3, 7, 5, 6, 4, 2, 10, 9, 8], having piles [[2, 3], [4, 5, 7], [6], [8, 9, 10]]
At level 0 status for sequence [2, 7, 5, 6, 4, 2, 10, 9, 8], having piles [[3], [4, 5, 7], [6], [8, 9, 10]]
At level 1 status for sequence [2, 3, 5, 6, 4, 2, 10, 9, 8], having piles [[4, 5, 7], [8, 9, 10], [6]]
At level 2 status for sequence [2, 3, 4, 6, 4, 2, 10, 9, 8], having piles [[5, 7], [8, 9, 10], [6]]
At level 3 status for sequence [2, 3, 4, 5, 4, 2, 10, 9, 8], having piles [[6], [8, 9, 10], [7]]
At level 4 status for sequence [2, 3, 4, 5, 6, 2, 10, 9, 8], having piles [[7], [8, 9, 10]]
At level 5 status for sequence [2, 3, 4, 5, 6, 7, 10, 9, 8], having piles [[8, 9, 10]]
At level 6 status for sequence [2, 3, 4, 5, 6, 7, 8, 9, 8], having piles [[9, 10]]
At level 7 status for sequence [2, 3, 4, 5, 6, 7, 8, 9, 8], having piles [[10]]
At level 8 status for sequence [2, 3, 4, 5, 6, 7, 8, 9, 10], having piles []
Finally! After patience sort input array is sorted [2, 3, 4, 5, 6, 7, 8, 9, 10]
Conclusion
Today we have seen a simple version of patience sort using priority queue, there are other ways to implement the same sort. Happy Sorting!
Credit and References
https://en.wikipedia.org/wiki/Patience_sorting
https://www.stat.berkeley.edu/~aldous/Research/OP/patience.pdf
