Алгоритм поиска и сортировки PHP: терпение

Алгоритм поиска и сортировки PHP: упражнение 16 с решением

Напишите программу PHP для сортировки списка элементов, используя сортировку Patience.
Сортировка терпения - это алгоритм сортировки, вдохновленный и названный в честь терпения карточной игры. Вариант алгоритма эффективно вычисляет длину самой длинной увеличивающейся подпоследовательности в данном массиве.
Название алгоритма происходит от упрощенного варианта карточной игры терпения. Эта игра начинается с перемешанной колоды карт. Эти карты раздаются одна за другой в последовательность стопок на столе в соответствии со следующими правилами.

• Изначально свай нет. Первая сданная карта образует новую колоду, состоящую из одной карты.
• Каждая последующая карта помещается в крайнюю левую существующую стопку, чья верхняя карта имеет значение, большее или равное значению новой карты, или справа от всех существующих стопок, образуя новую стопку.
• Когда карт больше не осталось, игра заканчивается.

Эта карточная игра превращается в алгоритм двухфазной сортировки следующим образом. Учитывая массив из n элементов из некоторого полностью упорядоченного домена, рассмотрите этот массив как набор карт и смоделируйте игру сортировки терпения. Когда игра закончится, восстановите отсортированную последовательность, неоднократно отбирая минимально видимую карту; Другими словами, выполните p-way слияние куч p, каждая из которых отсортирована внутри.

Пример решения:

PHP-код:

<?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);
?>

Пример вывода:

 массив                                                               
(                                                                   
    [0] => 100                                                      
    [1] => 54                                                       
    [2] => 7                                                        
    [3] => 2                                                        
    [4] => 5                                                        
    [5] => 4                                                        
    [6] => 1                                                        
)                 

Блок-схема:

Редактор кода PHP:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу PHP для сортировки списка элементов, используя сортировку Strand.
Далее: Напишите программу PHP для сортировки списка элементов с помощью сортировки слиянием.