Patience sorting es un algoritmo de clasificación basado en el juego de cartas Patience . En este algoritmo de clasificación, se utilizan las reglas del juego de la paciencia para clasificar una lista de elementos en función de sus valores.
Reglas del juego de la paciencia:
- Las cartas con un valor más bajo se pueden colocar sobre la carta.
- Si no hay una posición posible para una carta, se puede crear una nueva pila.
- El objetivo es formar tantas pilas como sea posible.
A continuación se muestra la visualización del juego de la siguiente manera:
Como en la visualización anterior, está claro que las cartas solo se colocan cuando el valor de las mismas es menor que la carta más alta de la pila. De lo contrario, si no existe tal pila, cree una nueva.
Clasificación de paciencia: generalmente hay dos pasos en la clasificación de paciencia que es la creación de las pilas y la fusión de las pilas. A continuación se muestra la ilustración de los pasos:
- Inicialice una array 2D para almacenar las pilas.
- Recorra la array dada y realice las siguientes operaciones:
- Itere sobre todas las pilas y verifique que la parte superior de la pila de cada pila sea menor que el elemento actual o no. SI se encuentra que es cierto, luego empuje el elemento actual a la parte superior de la pila.
- De lo contrario, cree una nueva pila con el elemento actual como la parte superior de esa pila.
- Merge the Piles: La idea es realizar una fusión de k vías de los p montones, cada uno de los cuales se ordena internamente. Itere sobre todas las pilas mientras el recuento de elementos en la pila sea mayor o igual a 0 y encuentre el elemento mínimo desde la parte superior de cada pila y empújelo a la array ordenada.
A continuación se muestra la visualización de los pasos de clasificación:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to merge piles in a sorted order
vector<int> merge_piles(vector<vector<int> >& v)
{
// Store minimum element from
// the top of stack
vector<int> ans;
// In every iteration find the smallest element
// of top of pile and remove it from the piles
// and store into the final array
while (1) {
// Stores the smallest element
// of the top of the piles
int minu = INT_MAX;
// Stores index of the smallest element
// of the top of the piles
int index = -1;
// Calculate the smallest element
// of the top of the every stack
for (int i = 0; i < v.size(); i++) {
// If minu is greater than
// the top of the current stack
if (minu > v[i][v[i].size() - 1]) {
// Update minu
minu = v[i][v[i].size() - 1];
// Update index
index = i;
}
}
// Insert the smallest element
// of the top of the stack
ans.push_back(minu);
// Remove the top element from
// the current pile
v[index].pop_back();
// If current pile is empty
if (v[index].empty()) {
// Remove current pile
// from all piles
v.erase(v.begin() + index);
}
// If all the piles are empty
if (v.size() == 0)
break;
}
return ans;
}
// Function to sort the given array
// using the patience sorting
vector<int> patienceSorting(vector<int> arr)
{
// Store all the created piles
vector<vector<int> > piles;
// Traverse the array
for (int i = 0; i < arr.size(); i++) {
// If no piles are created
if (piles.empty()) {
// Initialize a new pile
vector<int> temp;
// Insert current element
// into the pile
temp.push_back(arr[i]);
// Insert current pile into
// all the piles
piles.push_back(temp);
}
else {
// Check if top element of each pile
// is less than or equal to
// current element or not
int flag = 1;
// Traverse all the piles
for (int j = 0; j < piles.size(); j++) {
// Check if the element to be
// inserted is less than
// current pile's top
if (arr[i] < piles[j][piles[j].size() - 1]) {
piles[j].push_back(arr[i]);
// Update flag
flag = 0;
break;
}
}
// If flag is true
if (flag) {
// Create a new pile
vector<int> temp;
// Insert current element
// into temp
temp.push_back(arr[i]);
// Insert current pile
// into all the piles
piles.push_back(temp);
}
}
}
// Store the sorted sequence
// of the given array
vector<int> ans;
// Sort the given array
ans = merge_piles(piles);
// Traverse the array, ans[]
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 6, 12, 2, 8, 3, 7 };
// Function Call
patienceSorting(arr);
}
Javascript
<script>
// Javascript program of the above approach
// Function to merge piles in a sorted order
function merge_piles(v) {
// Store minimum element from
// the top of stack
let ans = [];
// In every iteration find the smallest element
// of top of pile and remove it from the piles
// and store into the final array
while (1) {
// Stores the smallest element
// of the top of the piles
let minu = Number.MAX_SAFE_INTEGER;
// Stores index of the smallest element
// of the top of the piles
let index = -1;
// Calculate the smallest element
// of the top of the every stack
for (let i = 0; i < v.length; i++) {
// If minu is greater than
// the top of the current stack
if (minu > v[i][v[i].length - 1]) {
// Update minu
minu = v[i][v[i].length - 1];
// Update index
index = i;
}
}
// Insert the smallest element
// of the top of the stack
ans.push(minu);
// Remove the top element from
// the current pile
v[index].pop();
// If current pile is empty
if (v[index].length == 0) {
// Remove current pile
// from all piles
v.splice(index, 1);
}
// If all the piles are empty
if (v.length == 0)
break;
}
return ans;
}
// Function to sort the given array
// using the patience sorting
function patienceSorting(arr) {
// Store all the created piles
let piles = [];
// Traverse the array
for (let i = 0; i < arr.length; i++) {
// If no piles are created
if (piles.length == 0) {
// Initialize a new pile
let temp = [];
// Insert current element
// into the pile
temp.push(arr[i]);
// Insert current pile into
// all the piles
piles.push(temp);
}
else {
// Check if top element of each pile
// is less than or equal to
// current element or not
let flag = 1;
// Traverse all the piles
for (let j = 0; j < piles.length; j++) {
// Check if the element to be
// inserted is less than
// current pile's top
if (arr[i] < piles[j][piles[j].length - 1]) {
piles[j].push(arr[i]);
// Update flag
flag = 0;
break;
}
}
// If flag is true
if (flag) {
// Create a new pile
let temp = [];
// Insert current element
// into temp
temp.push(arr[i]);
// Insert current pile
// into all the piles
piles.push(temp);
}
}
}
// Store the sorted sequence
// of the given array
let ans = [];
// Sort the given array
ans = merge_piles(piles);
// Traverse the array, ans[]
for (let i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
return ans;
}
// Driver Code
let arr = [6, 12, 2, 8, 3, 7];
// Function Call
patienceSorting(arr);
// This code is contributed by _saurabh_jaiswal.
</script>
2 3 6 7 8 12
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Nota: El enfoque anterior se puede optimizar mediante la fusión de montones utilizando la cola de prioridad .
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
</br>función playGif(){ </br> var gif = document.getElementById(‘gif’); </br> if (gif.src == “https://media.geeksforgeeks.org/wp-content/uploads/20200501171647/Patience.gif”){ </br> gif.src = “https://media .geeksforgeeks.org/wp-content/uploads/20200501175532/base2.jpg”; </br> }else{ </br> gif.src = “https://media.geeksforgeeks.org/wp-content/uploads/20200501171647/Patience.gif”; </br> } </br>} </br>función playSortingGif(){ </br> var gif1 = document.getElementById(‘clasificación’); </br> var gif2 = documento.getElementById(‘clasificar_gif1’); </br> gif1.style.display = “ninguno”; </br> gif2.style.display = “bloquear”; </br>}</br>function pauseSortingGif(){ </br> var gif1 = document.getElementById(‘clasificación’); </br> var gif2 = documento. getElementById(‘ordenar_gif1’); </br> gif1.style.display = “bloquear”; </br> gif2.style.display = “ninguno”; </br>} </br>