# 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.

**What is the difficulty level of this exercise?**

Test your Programming skills with w3resource's quiz.

**Weekly Trends and Language Statistics**- Weekly Trends and Language Statistics