PHP Searching and Sorting Algorithm: Strand sort

PHP Searching and Sorting Algorithm: Exercise-15 with Solution

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.

Sample Solution :

PHP Code :

<?php
// Create a new instance of SplDoublyLinkedList
$lst = new SplDoublyLinkedList();

// Iterate over the array and push each element into the linked list
foreach (array(100, 0, 2, 5, -1, 4, 1) as $v)
    $lst->push($v);

// Call the strandSort function to sort the linked list and iterate over the sorted elements
foreach (strandSort($lst) as $v)
    echo "$v ";

echo " " . PHP_EOL;

// Function to perform Strand Sort on a SplDoublyLinkedList
function strandSort(SplDoublyLinkedList $lst) {
    // Initialize an empty list to store the sorted elements
    $result = new SplDoublyLinkedList();

    // Continue until the input list is empty
    while (!$lst->isEmpty()) {
        // Initialize two lists: one to store the sorted elements and the other to store the remaining elements
        $sorted = new SplDoublyLinkedList();
        $remain = new SplDoublyLinkedList();

        // Move the first element from the input list to the sorted list
        $sorted->push($lst->shift());

        // Iterate over the remaining elements in the input list
        foreach ($lst as $item) {
            // Compare the top element of the sorted list with the current element
            // If the current element is greater than or equal to the top element, add it to the sorted list
            // Otherwise, add it to the remaining list
            if ($sorted->top() <= $item) {
                $sorted->push($item);
            } else {
                $remain->push($item);
            }
        }

        // Merge the sorted list with the result list
        $result = _merge($sorted, $result);

        // Update the input list to contain the remaining elements
        $lst = $remain;
    }

    // Return the sorted result list
    return $result;
}

// Function to merge two sorted lists
function _merge(SplDoublyLinkedList $left, SplDoublyLinkedList $right) {
    // Initialize an empty list to store the merged result
    $res = new SplDoublyLinkedList();

    // Continue until both lists are empty
    while (!$left->isEmpty() && !$right->isEmpty()) {
        // Compare the bottom elements of both lists
        // If the bottom element of the left list is smaller, remove and add it to the result list
        // Otherwise, remove and add the bottom element of the right list to the result list
        if ($left->bottom() <= $right->bottom()) {
            $res->push($left->shift());
        } else {
            $res->push($right->shift());
        }
    }

    // Add any remaining elements from the left list to the result list
    foreach ($left as $v)
        $res->push($v);

    // Add any remaining elements from the right list to the result list
    foreach ($right as $v)
        $res->push($v);

    // Return the merged result list
    return $res;
}
?>

Output:

-1 0 1 2 4 5 100 

Explanation:

In the exercise above,

• Initialization and input:
• An instance of "SplDoublyLinkedList" named '$lst' is created to store the input elements.
• The input array [100, 0, 2, 5, -1, 4, 1] is iterated over, and each element is pushed onto the doubly linked list.
• Strand Sort Function (strandSort):
• This function takes a doubly linked list '$lst' as input and sorts it using the Strand Sort algorithm.
• The function starts by initializing an empty list named '$result' to store the sorted elements.
• The sorting process continues until the input list is empty.
• During each iteration, two additional lists are created: '$sorted' to store sorted elements and '$remain' to store remaining elements.
• The first element from the input list is moved to the '$sorted' list.
• Next, each element is examined:
• If the element is greater than or equal to the top element of the '$sorted' list, it is appended to the '$sorted' list.
• Otherwise, it is appended to the '$remain' list.
• After processing all elements in the input list, the sorted list '$sorted' is merged with the '$result' list using the "_merge()" function.
• The input list '$lst' is updated to contain the remaining elements stored in the '$remain' list.
• Merge Function (_merge):
• This function takes two sorted doubly linked lists ('$left' and '$right') as input and merges them into a single sorted list.
• An empty list named '$res' is initialized to store the merged result.
• Elements are iteratively removed from the bottom of '$left' and '$right' lists and added to '$res' in sorted order.
• After one of the lists becomes empty, any remaining elements in the other list are added to '$res'.
• Finally, the merged result list '$res' is returned.
• Output:
• After sorting the input list using the "strandSort()" function, the sorted elements are retrieved one by one using a "foreach" loop and printed to the console.

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 Bogo sort.
Next: Write a PHP program to sort a list of elements using Patience sort.