﻿ PHP: Sort a list of elements using Patience sort - 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
(
 => 100
 => 54
 => 7
 => 2
 => 5
 => 4
 => 1
)
```

Flowchart : PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

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;

\$this->a += \$a;
return \$this;
}

public function get() {
return \$this->a;
}
}
\$object = new MyClass();
```

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

```class MyClass {
private \$a = 0;
\$this->a += \$a;
return \$this;
}
public function get() {
return \$this->a;
}
}
\$o1 = new MyClass();
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
```