Bogo Sort In PHP

23rd June 2018 - 4 minutes read time

Note: This post is over a year old and so the information contained here might be out of date. If you do spot something please leave a comment and I will endeavour to correct.

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.

PHP

sort

Add new comment

Related Content

Creating A Game With PHP Part 4: Side Scrolling Shooter

As another step up from the game of snake I created in my last post I decided to try my hand at creating a side scrolling shooter. Just like my other posts, this is an ASCII based game played on the command line.

A side scrolling shooter, if you didn't already know, moves a scene from right to left across the screen with enemies moving with the scene towards the player's ship, which is on the left hand side of the scene. The player can fire bullets towards the enemies so remove them from the scene.

Seeding Random Numbers in PHP

Computers are not that great at creating random numbers as the methods they use are deterministic. That is, they start from a number (called a seed) and apply maths to that number to generate pseudorandom numbers. Most random numbers generated by computers programs use a seed provided by the system, which is generally the current time. If you can guess the initial value then you can start to work out what the random sequence of numbers generated is. Most random numbers, are therefore not suitable for encryption.

PHP: Find An Array Sequence In An Array

I was looking for a function that searched an array for another array, and after not finding one I decided to write it. What I was looking for was a function that took a smaller array and searched for that exact sequence of items in a larger array. As it happens, PHP does have a number of array search functions, but they didn't produce the correct result.

PHP Live Regex

When creating regular expressions for PHP I tend to use the awesome tool PHP Live Regex.

This tool has really helped me over the last couple of years to create regular expressions for many of the projects I've been working on. Everything from validation functions to formatters that use regular expressions have had their expressions worked out using this tool. I even use it for testing one off expressions where I just need to find/replace in a file.

PHP Strict Types

In December 2015, PHP 7 introduced scalar type declarations and with it the strict_types flag. This flag can be used to enforce the type of value passed to functions. Although I have seen it in action in the past, I have never actually used it before so I decided to look into it a little to see what it was about.

PHP instanceof Operator Tips

The instanceof operator in PHP is great at making sure you are looking at a type of object before acting on it. Whilst it's straightforward to use on its own, using it can lead to some undesirable side effects.

As a basic example, let's create a couple of interfaces and classes to show the instanceof operator in action. Rather than just have some test names I am using object names that you might find in a system. This consists of User and Order that might form part of a commerce system.