w3resource

Python: Sort unsorted numbers using Patience sorting

Python Search and Sorting : Exercise-34 with Solution

Write a Python program to sort unsorted numbers using patience sorting.

From Wikipedia:
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array.
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.
1. nitially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2. 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.
3. When there are no more cards remaining to deal, the game ends.

Sample Solution:

Python Code:

#Ref.https://bit.ly/2YiegZB
from bisect import bisect_left
from functools import total_ordering
from heapq import merge
@total_ordering
class Stack(list):
    def __lt__(self, other):
        return self[-1] < other[-1]
    def __eq__(self, other):
        return self[-1] == other[-1]
def patience_sort(collection: list) -> list:
    stacks = []
    # sort into stacks
    for element in collection:
        new_stacks = Stack([element])
        i = bisect_left(stacks, new_stacks)
        if i != len(stacks):
            stacks[i].append(element)
        else:
            stacks.append(new_stacks)

    # use a heap-based merge to merge stack efficiently
    collection[:] = merge(*[reversed(stack) for stack in stacks])
    return collection            
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
patience_sort(nums)
print("Sorted order is:", nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
patience_sort(nums)
print("Sorted order is:", nums)

Sample Output:

Original list:
[4, 3, 5, 1, 2]
Sorted order is: [1, 2, 3, 4, 5]

Original list:
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
Sorted order is: [-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178]

Flowchart:

Flowchart: Python Data Structures and Algorithms: Sort unsorted numbers using Patience sorting.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort unsorted numbers using Pigeonhole sorting.
Next: Write a Python program to sort an odd–even sort or odd–even transposition sort.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://198.211.115.131/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-34.php