“Two things define you: your patience when you have nothing and your attitude when you have everything.” — George Bernard Shaw.
What is Patience Sorting?
Patience sorting is a comparison-based sorting algorithm that gradually sorts an array of elements by repeatedly applying a simple swap operation. It is known for its simple implementation and good performance for small to medium-sized arrays.
The basic idea behind patience sorting is to partition the array into two parts, an ordered part at the beginning and an unordered part at the end, and then repeatedly swap elements from the unordered part into the ordered part until the entire array is sorted.
It can be used to identify longest increasing sub sequence in an array.
Let’s see the below example :
We have an array and have values like [10, 9, 2, 5, 3, 7, 101, 18]. The number of piles created is the length of longest increasing sub sequence. Whenever a card is placed on top of a pile, put a back-pointer to the top card in the previous pile (that, by assumption, has a lower value than the new card has). In the end, follow the back-pointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm.
arr = [10, 9, 2, 5, 3, 7, 101, 18]class Solution(object):
def lengthOfLIS(self, nums):
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i + j) // 2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(patienceSort(arr))
Output : We have 4 piles here
[[10, 9, 2], [5, 3], [7], [101, 18]]Why it is called as Patience sort?
The algorithm’s name derives from a simplified variant of the patience card game. The game begins with a shuffled deck of cards. The cards are dealt one by one into a sequence of piles on the table, according to the following rules.
- Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
- 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.
- When there are no more cards remaining to deal, the game ends.
This card game is turned into a two-phase sorting algorithm, as follows. Given an array of n elements from some totally ordered domain, consider this array as a collection of cards and simulate the patience sorting game. When the game is over, recover the sorted sequence by repeatedly picking off the minimum visible card; in other words, perform a k-way merge of the p piles, each of which is internally sorted. You can play it here.
A little bit of history
Patience sorting was named by C. L. Mallows, who attributed its invention to A.S.C. Ross in the early 1960s. According to Aldous and Diaconis, patience sorting was first recognized as an algorithm to compute the longest increasing subsequence length by Hammersley. A.S.C. Ross and independently Robert W. Floyd recognized it as a sorting algorithm. Initial analysis was done by Mallows. Floyd’s game was developed by Floyd in correspondence with Donald Knuth.
The complexities
Time Complexity:
- Worst case: O(n²) — When the array is reverse-sorted or has a lot of swaps.
- Average case: O(n log n) — Expected to be better than the worst case for a random array.
Space Complexity:
- Patience sorting requires only O(1) additional space for auxiliary storage, making it an in-place sorting algorithm.
Patience sorting is not as efficient as some other well-known sorting algorithms like merge sort or quick sort for large arrays, but its simplicity and good performance for small to medium-sized arrays make it an attractive choice in certain situations.
For any type of help regarding career counselling, resume building, discussing designs or know more about latest data engineering trends and technologies reach out to me at anigos.
P.S : I don’t charge money
