PHP Searching and Sorting Algorithm: Bogo sort

PHP Searching and Sorting Algorithm: Exercise-14 with Solution

Write a PHP program to sort a list of elements using Bogo sort.

In computer science, bogosort is a particularly ineffective sorting algorithm based on the generate and test paradigm. The algorithm successively generates permutations of its input until it finds one that is sorted. It is not useful for sorting but may be used for educational purposes, to contrast it with other more realistic algorithms.

Sample Solution :

PHP Code :

<?php
// Function to check if a list is sorted in ascending order
function issorted($list)
{
    // Get the count of elements in the list
    $cnt = count($list);
    // Iterate through the list elements starting from the second element
    for($j = 1; $j < $cnt; $j++)
    {
        // If the previous element is greater than the current element, list is not sorted
        if($list[$j-1] > $list[$j])
		{
            return false; // Return false indicating list is not sorted
        }
    }
    return true; // Return true indicating list is sorted
}

// Function to perform Bogo Sort on a list
function bogo_sort($list)
{
    // Repeat shuffling until the list is sorted
    do
    {
        shuffle($list); // Shuffle the list
    }
    while(!issorted($list)); // Repeat until list is sorted
    return $list; // Return the sorted list
}

$test_array = array(100, 0, 2, 5, -1, 4, 1);
echo "\nOriginal Array :\n";
echo implode(', ',$test_array );
echo "\nSorted Array :\n";
echo implode(', ',bogo_sort($test_array)). PHP_EOL;
?>

Output:

Original Array :                                                    
100, 0, 2, 5, -1, 4, 1                                              
Sorted Array :                                                      
-1, 0, 1, 2, 4, 5, 100 

Explanation:

In the exercise above,

• The "issorted()" function is defined to check if a given list is sorted in ascending order. It iterates through the list and compares each element with its next element. If it finds any element that is greater than its next element, it returns 'false', indicating that the list is not sorted. If the loop completes without finding any unsorted elements, it returns 'true', indicating that the list is sorted.
• The "bogo_sort()" function implements the Bogo Sort algorithm. Bogo Sort repeatedly shuffles the list randomly until it is sorted. It calls the "shuffle()" function to randomly rearrange the elements of the list and then checks if the list is sorted using the "issorted()" function. It continues this process until the list is sorted.
• An example array 'test_array' is defined with some initial values.
• The original array is displayed using "echo".
• The "bogo_sort()" function is called with the 'test_array' as input. The sorted array returned by the function is then displayed using "echo".

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