Array Sorting Algorithms IV

This tutorial is the fourth installment of my "Array Sorting Algorithms" tutorial series. In this tutorial, I will be showing you a completely ineffective method of sorting arrays for educational and contrast purposes. Seriously... DO NOT EVER use the code I am about to show you in an actual program. Also, a basic knowledge of C++ (functions, arrays, etc...) is necessary to continue in this tutorial.

In previous tutorials, I have covered the Bubble sort, Insertion sort, and Quicksort algorithms. All of these algorithms work perfectly fine, but there is a reason for that. These algorithms rely on efficient code that works towards a beneficial outcome. However, there are several ways of sorting pieces of data, some that are not so efficient. Take the Bogosort algorithm for example (also known as monkey sort or shotgun sort). Bogosort sorts pieces of data by "shuffling" them (through the generation of pseudo random numbers) and then checking to see if they are sorted. If they are not sorted, the process repeats. So, first lets look at the pseudo code

fuction bogosort(array, length)
{
    while(!inOrder(array, length))
    {
        shuffle(array, length)
    }
}

function inOrder(array, length)
{
    for each element in array
        if the current element is greater than the next element 
            return false
    return true
}

function shuffle(array, length)
{
    for each element in the array
        set swapPosition to a random number
        swap the elements at the current position and a random position
}

Since Bogosort has basically two parts (checking to see if the array is in order and shuffling), I felt it would be best to break it up into two functions. So, when Bogosort first starts up, it checks to see if the array is in order. If it isn't, the array is shuffled then checked again for order. This continues until the array is in order. If you sat down with an unordered deck of cards and started shuffling - hoping to get them in the correct order - you would be doing the same thing this algorithm is doing. A side note: This algorithm is based on the Infinite Monkey Therom, which states that, given enough time, a monkey placed at a typewriter hitting random keys, could type the entire works of Shakespeare.

Now that we have the pseudo code, lets write the actual C++ code for this program. Open up a new C++ file in your favorite text editor and lets begin. First, type in the following lines:

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

void bogosort(int[], int);
void shuffle(int[], int);
bool inOrder(int[], int);

int main(void)
{
    int array[3];
    
    for(int i = 0; i < 3; i++)
    {
            cout << "Enter element " << i + 1 << " of the array to be sorted: ";
            cin >> array[i];
    }
    
    bogosort(array, 3);
    
    cout << "The sorted array is: ";
    
    for(int i = 0; i < 2; i++)
            cout << array[i] << ",";
    cout << array[2] << "\n";
}

As you can see here, this is basically a test program for our bogosort algorithm. First, I included iostream for output and defined the function prototypes that we are going to need. I also include stdlib.h and time.h for random number generation. Then I started constructing the main function. In this case, we ask the user for 3 numbers that we then store in the array. Using our bogosort algorithm, we sort the numbers (hopefully before next year) and output the sorted array to the user. Defiantly don't try to sort a set of data above 20 numbers.

Next, lets write the code for the functions we will be using in bogosort, and the bogosort algoritm itself. Type the following into your text editor below the code you just wrote:

void bogosort(int array[], int length)
{
     while(!inOrder(array, length))
          shuffle(array, length);
}

void shuffle(int array[], int length)
{
     srand(time(NULL));
     
     for(int i = 0; i < length; i++)
     {
          int swapPosition = rand() % length + 1;
          int temp = array[i];
          array[i] = array[swapPosition];
          array[swapPosition] = temp;
     }
}

bool inOrder(int array[], int length)
{
    for(int i = 0; i < length; i++)
    {
         if(array[i] > array[i+1])
              return false;
    }
    return true; 
}

This code is pretty much the same as our pseudo code was. Our bogosort function accepts an array and the length of the array as input and then checks to see if the order is correct. If the order isn't correct, bogosort shuffles the deck and checks to see if the order is correct again. This continues until the order is right.

A word about running this program. It may look like your computer has frozen because there will be no activity in the console while the program is running. Don't worry though. Once the algorithm gets the right order, it will output the result. It is possible that you get lucky though and get the right order right away.

So, you may be asking yourself, "This algorithm is really stupid and it doesn't work at all... why are we looking at it?" The explanation for this is rather simple. This algorithm is a great example of code that runs and does its job, just in a completely ineffective way. If you saw this code running in one of the programs that your team was writing, you would probably flip your lid and start asking questions like, "Who thought it was a good idea to let a monkey holding a shotgun sort our data?" The fact is that to know good code, you have to look at a few pieces of bad code and understand why the code is bad. This allows you to analyze bad code in the future and understand what needs to be fixed. A side note: If you came to this tutorial looking for a real sorting algorithm, please take a look at the rest of the array sorting algorithms tutorial series: Array Sorting Algorithms I, Array Sorting Algorithms II, and Array Sorting Algorithms III.

The code for this tutorial was written and compiled using the Dev-C++ compiler. It may need some tweaking in order to run in other compilers. The source code used in this project is attached for convenience. If you would like to contribute to the information presented here, or would like to offer corrections, please post a reply.