Bogo Sort In PHP

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.

1. Take an array.
2. Shuffle it.
3. If the array sorted then stop.
4. 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.