PHP Searching and Sorting Algorithm: Patience sort
PHP Searching and Sorting Algorithm: Exercise-16 with Solution
Write a PHP program to sort a list of elements using Patience sort.
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. This game begins with a shuffled deck of cards. These 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 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 order words, perform an p-way merge of the p piles, each of which is internally sorted.
Sample Solution :
PHP Code :
<?php
class PilesHeap extends SplMinHeap {
public function compare($pile1, $pile2) {
return parent::compare($pile1->top(), $pile2->top());
}
}
function patience_sort($n) {
$piles = array();
// sort into piles
foreach ($n as $x) {
// binary search
$low = 0; $high = count($piles)-1;
while ($low <= $high) {
$mid = (int)(($low + $high) / 2);
if ($piles[$mid]->top() >= $x)
$high = $mid - 1;
else
$low = $mid + 1;
}
$i = $low;
if ($i == count($piles))
$piles[] = new SplStack();
$piles[$i]->push($x);
}
// priority queue allows us to merge piles efficiently
$heap = new PilesHeap();
foreach ($piles as $pile)
$heap->insert($pile);
for ($c = 0; $c < count($n); $c++) {
$smallPile = $heap->extract();
$n[$c] = $smallPile->pop();
if (!$smallPile->isEmpty())
$heap->insert($smallPile);
}
assert($heap->isEmpty());
}
$a = array(100, 54, 7, 2, 5, 4, 1);
patience_sort($a);
print_r($a);
?>
Sample Output:
Array ( [0] => 100 [1] => 54 [2] => 7 [3] => 2 [4] => 5 [5] => 4 [6] => 1 )
Flowchart :

PHP Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
Previous: Write a PHP program to sort a list of elements using Strand sort.
Next: Write a PHP program to sort a list of elements using Merge sort.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends
- Python Interview Questions and Answers: Comprehensive Guide
- Scala Exercises, Practice, Solution
- Kotlin Exercises practice with solution
- MongoDB Exercises, Practice, Solution
- SQL Exercises, Practice, Solution - JOINS
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- JavaScript String Exercises
- JavaScript HTML Form Validation
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join