﻿ PHP: Sort a list of elements using Strand sort - w3resource

# 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

// 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
// Initialize an empty list to store the sorted elements

// 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

// 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
// Initialize an empty list to store the merged result

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

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿