Interactive Programming Education Platform

Logic Practice

Sorting algorithms play a crucial role in computer science, serving as the foundation for various applications and systems. Despite being less well-known compared to Quick Sort or Merge Sort, Patience Sort stands out as a highly effective technique. Its efficiency is noteworthy, boasting a time complexity of O(nlogn) and drawing inspiration from the strategic gameplay of the card game Patience or Solitaire.

The technique is known as Patience Sort, deriving its name from a card game where players arrange cards into separate piles. This sorting algorithm is intriguing as it mimics the practical actions of the game, involving card organization, a process that can be engaging for kids to grasp. Even though Patience Sort is a theoretical model and not applied for actual data sorting, its straightforward methodology and effectiveness in tackling specific challenges, like determining the longest increasing subsequence's length, render it a valuable addition to a developer's toolkit.

In this article, we are going to dissect the fundamental concept of the Patience Sort algorithm and delve into its operational process. We will additionally explain the implementation of Patience Sort in C++ and detail the steps for its practical application. Furthermore, we will delve into the time and space complexity of Patience Sort. By the conclusion of this piece, readers will have a comprehensive understanding of how Patience Sort functions and the potential applications it offers.

Understanding the Concept

Essentially, the Patience Sort algorithm mirrors the process seen in the patience card game, where cards are organized into stacks. The fundamental concept is to form multiple stacks in a way that each stack arranges elements in ascending order from top to bottom. The sorting process involves grouping each element of the input array into one of these stacks based on specific criteria, and then merging the stacks to produce the sorted array.

Pile Creation

The first process in Patience Sort is to sort the objects into piles. Every member of the array is put in a pile in a manner that ensures that all piles consist of elements in increasing order. The rules for placing an element onto a pile are as follows:

✅ Locate the first of the heaps, the top element of which (card) is not less than the current one.
✅ Stack this pile with the element on top of it.
✅ If no such pile is available, the current element is used to make a new pile, which initially contains only the current element.
✅ By applying binary search, we will be able to quickly find the right pile for each of the elements. Binary search helps us to easily find out the pile that should be used to place the element, thus making the algorithm efficient O(nlogn) time.

Merging Piles

The subsequent stage following the sorting and arrangement of all elements into piles involves merging these piles to construct the sorted array. This merging process involves iterating through the collection of piles and, at each iteration, selecting the smallest element from the top of each pile and adding it to the sorted array. This operation can be facilitated using a min-heap (also known as a priority queue) and will have a time complexity of O(m).

A minimum heap allows us to efficiently locate and remove the smallest element from the heap. As each minimum element is extracted, the subsequent element from the heap replaces it. This sequence repeats until all elements are removed, resulting in a sorted array with elements in ascending order.

Step-by-Step Algorithm for Patience Sort

Patience Sort presents a fascinating approach inspired by the patience card game. It functions by forming and merging n stacks of items, ensuring that the sorting process remains efficient with a time complexity of O(n log n). The following is a thorough and precise theoretical explanation of the examined algorithm's sequential operations.

Step 1: Initialization

Upon initialization, the algorithm sets the list of piles to an empty state. Each pile is expected to contain elements sorted in ascending order from top to bottom. Since there are no elements present initially, there are no piles to sort at this point.

Step 2: Creating Piles

The initial stage of the algorithm is executed through the main loop, where every item from the input array is sorted into the correct stack. Let's delve into a comprehensive explanation of this procedure:

Iterate Through Elements:

If we aim to iterate through each element in the given array, the traversal process is outlined below:

Find the Correct Pile:

For every individual item, identify the leftmost stack where the uppermost card (item) is equal to or greater than the present item. This technique ensures that each stack is arranged in a way that the stacks are organized in ascending order.

✅ To easily pinpoint this stack, implement a binary search. Utilizing binary search facilitates locating the correct stack with a time complexity of logarithm base n, which decreases this process from O(n) to O(log n).
✅ In case such a stack is present, place the item on top of it. If an exhaustive search yields no suitable stack, the current item is then added to its own separate stack.

Place the Element:

✅ Stack the current element on the pile identified or start building a new pile if the current one does not exist. Such placement ensures that the piles remain sorted in the manner indicated in the piles in the placement process.
✅ Sorting and placing the elements into piles is essential because after the merging, the size of these piles should represent the number of comparisions made and each next step in sorting is dependent on the previous one so it's easy to predict its outcome based on the outcomes of previous steps.
✅ Naturally, this step also has the complexity of O(nlogn) by using binary search overall for the entire array.

After arranging all the components into piles, the next stage in the analysis involves merging these piles into one consolidated sorted list. This merging operation utilizes a min-heap (also known as a priority queue) to extract the smallest element from the top of each pile. Below is a detailed explanation of how the merging process operates:

Insert Initial Elements:

✅ First, it is necessary to build a min heap, which is a heap filled with pairs, which contain a number and a reference to the pile index. The use of the min-heap enables the extraction of the least number on top of the pile among all the piles.
✅ The top element of each pile should be put into the min-heap. In addition to the element number, save the pile index for each to indicate which pile it belongs to.
✅ Thus, given that there are k piles, the heap is going to consist of k elements at the beginning.

Extract and Replace:

Similarly, if there is another item within the heap at the specified location, replace the removed item with the subsequent one. This ensures the heap remains at a consistent size and ensures that each item will eventually be involved in the operation.

Go on doing this process of extraction and replacement until the last item in the heap has been gotten. Every extraction and replacement operation guarantees, that the heap's smallest element is always situated at the top of the heap, for it to remain correctly sorted.

✅ Pop the first element of the min-heap and return. This element is guaranteed to be the smallest among all the present pile tops.
✅ Put this extracted element on the sorted array.
✅ The operations on min-heap, namely insertion and extraction, take a time of O(Log n)
✅ O(logk), where k is generally the number of piles. Due to the insertion and the extract operation, each element is only inserted and extracted once. Therefore, the merging step is of O(log).

Step 4: Result

Once the merging process is completed, the items from the stacks will be integrated into the array and arranged in ascending order. The algorithm ensures that the end result of the software will contain ordered elements in contrast to the function invocation.

Code Implementation:

Example


#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <queue> 
  
using namespace std; 
  
// Function to perform patience sorting given below
vector<int> patienceSort(const vector<int>& arr) { 
vector<vector<int>> piles;  // Step 1: Initialization of the sort(empty list of piles) 
  
// Step 2: Creating Piles 
for (int x : arr) { 
// Step 3: Binary Search for Placement 
auto it = lower_bound(piles.begin(), piles.end(), x,  
            [](const vector<int>& pile, int value) { return pile.back() < value; }); 
         
// Step 4: Pile Creation and Placement 
if (it != piles.end()) { 
it->push_back(x); 
} else { 
            piles.push_back(vector<int>(1, x)); 
} 
} 
  
// Step 5: Merging Piles 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; 
for (int i = 0; i < piles.size(); ++i) { 
        pq.emplace(piles[i].back(), i); 
piles[i].pop_back(); 
} 
  
vector<int> sortedArr; 
while (!pq.empty()) { 
auto [value, index] = pq.top(); 
        pq.pop(); 
        sortedArr.push_back(value); 
if (!piles[index].empty()) { 
            pq.emplace(piles[index].back(), index); 
piles[index].pop_back(); 
} 
} 
  
// Step 6: Final Sorted Array 
return sortedArr; 
} 
  
int main() { 
vector<int> arr; 
int n; 
  
// Prompt the user for the number of elements 
    cout << "Enter the number of elements: "; 
    cin >> n; 
  
// Prompt the user for the elements 
    cout << "Enter the elements: "; 
for (int i = 0; i < n; ++i) { 
int element; 
        cin >> element; 
        arr.push_back(element); 
} 
  
// Display the original array 
    cout << "Original array: "; 
for (int x : arr) { 
        cout << x << " "; 
} 
    cout << endl; 
  
// Perform Patience Sort 
vector<int> sortedArr = patienceSort(arr); 
  
// Display the sorted array 
    cout << "Sorted array: "; 
for (int x : sortedArr) { 
        cout << x << " "; 
} 
    cout << endl; 
  
return 0; 
}

Output:

Output


Enter the number of elements: 8 
Enter the elements: 6 3 8 1 5 2 7 4 
Original array: 6 3 8 1 5 2 7 4  
Sorted array: 1 2 3 4 5 6 7 8

Pros of Patience Sort

✅ Intuitive Concept: Patience Sort resembles a card game; therefore, the user should not experience any difficulties in visualizing this task. This makes the process rather easy to understand by new users especially about the sorting process.
✅ Optimal Time Complexity: The time of the algorithm is equal to O(n log n) which is the best complexity for using comparison. It makes it efficient for big data sets to compute because of the reduced time it takes to process elements in a data set.
✅ Application in Longest Increasing Subsequence: Application in Longest Increasing Subsequence: Patience Sort is very useful when finding the Longest Increasing Subsequence of a sequence. Such application is useful in numerous fields, including, but not limited to bioinformatics and data analysis.
✅ Stable Sorting: The algorithm is stable and, correspondingly, provides the preservation of the relative arrangement of elements equated to zero. This property becomes useful when the position of similar elements matters.
✅ Simplicity in Implementation: Surprisingly, making use of Patience Sort is extremely precise and consists of two elementary steps - binary search and min-heaps. This fact makes the programming language quite easier to code and debug during the development stage.

Cons of Patience Sort

✅ Not Practically Used: However, Patience Sort is not commonly applied in practice even though it has theoretical beauty. Other algorithms, such as Quick Sort or Merge Sort, are more often used solely because it is already known how they perform and where to find libraries that support them.
✅ Higher Space Complexity: Extra space is needed for the piles and the priority queue, bringing the space complexity of the algorithm to O(n). This can be a disadvantage especially in environments whereby memory is limited in the executing devices.
✅ Overhead of Binary Search and Heaps: The last feature worth mentioning that concerns this conclusion is the fact that both binary search and min-heaps increase time complexity and, to some extent, increase the algorithmic complexity, which in simpler cases can be solved by adopting simpler sorting algorithms.
✅ Less General-Purpose: The patience sort is slightly more intensive and less general compared to many other sorts. This Algorithm is specifically designed for finding subsequences while it is not a general solution for sorting.

Patience Sort In C++