Q:

Write a PHP program to sort a list of elements using Strand sort

0

Write a PHP program to sort a list of elements using Strand sort.
This is a way of sorting numbers by extracting shorter sequences of already sorted numbers from an unsorted list.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

<?php
$lst = new SplDoublyLinkedList();
foreach (array(100, 0, 2, 5, -1, 4, 1) as $v)
    $lst->push($v);
foreach (strandSort($lst) as $v)
    echo "$v ";
echo " ".PHP_EOL;
function strandSort(SplDoublyLinkedList $lst) {
    $result = new SplDoublyLinkedList();
    while (!$lst->isEmpty()) {
        $sorted = new SplDoublyLinkedList();
        $remain = new SplDoublyLinkedList();
        $sorted->push($lst->shift());
        foreach ($lst as $item) {
            if ($sorted->top() <= $item) {
                $sorted->push($item);
            } else {
                $remain->push($item);
            }
        }
        $result = _merge($sorted, $result);
        $lst = $remain;
    }
    return $result;
}
function _merge(SplDoublyLinkedList $left, SplDoublyLinkedList $right) {
    $res = new SplDoublyLinkedList();
    while (!$left->isEmpty() && !$right->isEmpty()) {
        if ($left->bottom() <= $right->bottom()) {
            $res->push($left->shift());
        } else {
            $res->push($right->shift());
        }
    }
    foreach ($left as $v)  $res->push($v);
    foreach ($right as $v) $res->push($v);
    return $res;
}
?>

Sample Output:

-1 0 1 2 4 5 100

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Similar questions


need a help?


find thousands of online teachers now