I came across this sorting algorithm the other day called 'bogo sort'. This is a sort of joke sorting algorithm that is highly ineffective at actually sorting arrays. The name comes from the word 'bogus'.
Here is how it works.
- Take an array.
- Shuffle it.
- If the array sorted then stop.
- If the array is not sorted then return to step 2.
As you can see, this isn't so much a sorting algorithm, more of a game of chance. Due to the random nature of the sort you might need to wait a very long time before the array is actually sorted.
Here is an implementation of a bogo sort in PHP.
/** * Sort an array using a bogo sort algorithm. * * @param array $array * The array to sort. * * @return array * The sorted array. */ function bogoSort($array) { // Assume array is unsorted. $sorted = FALSE; while ($sorted == FALSE) { // Keep running until the array is sorted. for ($i = 0; $i < count($array) - 1;++$i) { // Loop through the array and check that it has been sorted. if ($array[$i] > $array[$i + 1]) { // The array has not been sorted, so break out of the check loop. $sorted = FALSE; break; } // If we get to this point then the array is sorted. $sorted = TRUE; } if ($sorted) { // Array is sorted, return it. return $array; } // Shuffle the array. shuffle($array); } }
So why make this? Just for fun really. I had a good chuckle the first time I heard about this sorting algorithm so I had to have a god at implementing one. This algorithm is often used for educational purposes as a worst case scenario. The bogo sort is usually slower than a unidirectional bubble sort.
The mechanism of the bogo sort means that the length of the array dramatically increases the time taken to sort it. Sorting an array of under 5 items takes a few seconds (still quite a long time really). Sorting an array of more than 10 items takes a couple of minutes. I didn't test any more than 10 items in an array as I would be waiting for a very long time to sort.
As a quick test I decided to see how long the bogo sort actually took.
$times = []; for ($i = 0; $i <= 10; ++$i) { $time_start = microtime(true); $array = range(0, 10); shuffle($array); $array = bogoSort($array); $time_end = microtime(true); $times[] = $time_end - $time_start; } echo 'Total time: ' . (array_sum($times)) . 's Average time per sort: ' . (array_sum($times) / count($times)) . 's';
After quite a long time this is printed out.
Total time: 897.42127370834s Average time per sort: 81.583752155304
Sorting 10 arrays of 10 items takes a full 15 minutes.