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

PHP instanceof Operator

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.

Steganography With Images In PHP

Steganography is the practice of placing a secret message inside another message and only by looking at the original message in a different way can the hidden message be seen. This might be as mundane as writing a page of text and hiding a message in the text using the first letter of every sentence. Only by collecting the first letter of each sentence together can the hidden message be seen and read.

Modern steganography is defined as hiding a message (or file) inside a file. For example, you might look at an image and see an image, but if a message has been hidden you would also be able to extract it if you know where to look.

Color Sorting In PHP: Part 6

I finished my last post on sorting colors using PHP looking at incorporating all three dimensions into the display of the colors. This lead to some interesting displays of colors in discs using different shapes or lengths as an indication of the color in question. It was still lacking actually rendering out the third dimension in any meaingful way though.

As I am essentially looking at three dimensional data I thought about displaying the data as a cube in a 3D engine. I could then map the three dimensions of colors (red, green, blue) into the three dimensions of the 3D engine (x, y, z). This means creating a 3D scene with random color data and rendering that scene out. Funnily enough, there aren't a lot of people writing 3D rendering engines in PHP so I looked into writing a very basic version that would just show point data.

Extracting Data From An MP3 With PHP

I was looking at a media player on my phone the other day and was watching the waveform of the music shown on screen. This was a simple indication of the progress through the track and appeared to show quiet and loud sections of the track I was listening to. This got me thinking about how to extract this information as the media player I was watching must do this in real time in order to actually play the data, not just render this representation of the music.

After a bit of research into the MP3 file format I found that the file format is complex, but straight forward enough to process, so I decided to try and extract the data using PHP. I have seen a few techniques to extract the data from MP3 using PHP, but these largely involve applications like ffmpeg to convert the audio format into something like a WAV file, which is then processed.

Adding Arguments And Options To Deployer Tasks

I have been adding to my custom Deployer scripts for a number of months and I have now been using it to do more than just deploy my sites. Since it acts as a connection to my website server I have been using Deployer to perform other tasks like creating backups and clearing Drupal caches without having to log into the server to do it. What has helped me here is that I have set out my deployment tasks in a very modular fashion, so although my deployment runs a database backup, I there is nothing to stop me running the database backup command on it's own without doing a full deployment.