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.