w3resource

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 :

Flowchart: PHP - program of Patience sort

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.



PHP: Tips of the Day

Members of objects or classes can be accessed using the object operator (->) and the class operator (::).

Example:

class MyClass {
 public $a = 1;
 public static $b = 2;
 const C = 3;
 public function d() { return 4; }
 public static function e() { return 5; }
}
$object = new MyClass();
var_dump($object->a); // int(1)
var_dump($object::$b); // int(2)
var_dump($object::C); // int(3)
var_dump(MyClass::$b); // int(2)
var_dump(MyClass::C); // int(3)
var_dump($object->d()); // int(4)
var_dump($object::d()); // int(4)
var_dump(MyClass::e()); // int(5)
$classname = "MyClass"; 
var_dump($classname::e()); // also works! int(5)

Note that after the object operator, the $ should not be written ($object->a instead of $object->$a). For the class operator, this is not the case and the $ is necessary. For a constant defined in the class, the $ is never used.

Also note that var_dump(MyClass::d()); is only allowed if the function d() does not reference the object:

class MyClass {
 private $a = 1;
 public function d() {
 return $this->a;
 }
}
$object = new MyClass();
var_dump(MyClass::d()); // Error!

This causes a 'PHP Fatal error: Uncaught Error: Using $this when not in object context'

These operators have left associativity, which can be used for 'chaining':

class MyClass {
 private $a = 1;

 public function add(int $a) {
 $this->a += $a;
 return $this;
 }

 public function get() {
 return $this->a;
 }
}
$object = new MyClass();
var_dump($object->add(4)->get()); // int(5)

These operators have the highest precedence (they are not even mentioned in the manual), even higher that clone. Thus:

class MyClass {
 private $a = 0;
 public function add(int $a) {
 $this->a += $a;
 return $this;
 }
 public function get() {
 return $this->a;
 }
}
$o1 = new MyClass();
$o2 = clone $o1->add(2);
var_dump($o1->get()); // int(2)
var_dump($o2->get()); // int(2)

The value of $o1 is added to before the object is cloned!

Note that using parentheses to influence precedence did not work in PHP version 5 and older (it does in PHP 7):

// using the class MyClass from the previous code
$o1 = new MyClass();
$o2 = (clone $o1)->add(2); // Error in PHP 5 and before, fine in PHP 7
var_dump($o1->get()); // int(0) in PHP 7
var_dump($o2->get()); // int(2) in PHP 7