Bogosort
Today I am going to present one of the worst sorting algorithms, along with a C# implementation. The algorithm is called bogosort, also known by other names such as monkey sort, random sort or shotgun sort. This algorithm is very simple, and it works as follows:
1. Given a random array, check if it is sorted.
2. If it is not sorted, shuffle it randomly.
As you can imagine, this algorith is not very fast, but it CAN be very effective, and for an array just consisting of two elements, it is actually very nice. Despite this, don’t use it for practical purposes!
For a very detailed analysis of this algorithm, see the paper by H. Gruber, M. Holzer and O. Ruepp titled “Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms“.
Following is a C# implementation, which generates a random array, runs bogosort and then prints some nice statistics:
using System;
namespace Bogosort
{
class Program
{
private static System.Random rnd = new System.Random();
private static int compctr = 0;
static void Main(string[] args)
{
int[] array = GenRandomArray(6);
Console.WriteLine("Sorting a list of " + array.Length + " random numbers between 0 and " + 10 * array.Length + ".");
Console.Write("Original array: ");
PrintArray(array);
int i = 0;
System.DateTime startTime = System.DateTime.Now;
while (!Sorted(array))
{
array = Shuffle(array);
Console.Write("Shuffle " + i + ": ");
PrintArray(array);
i++;
}
System.DateTime stopTime = System.DateTime.Now;
Console.Write("The sorted array is: ");
PrintArray(array);
Console.WriteLine("This required " + i + " shufflings and took " + (stopTime-startTime).Milliseconds + " milliseconds.");
Console.WriteLine("The total number of comparisons made was " + compctr + ", which is " + (double)compctr / (double)i + " comparisons on average.");
Console.WriteLine("The total number of swaps made was " + array.Length * i + ".");
}
private static int Factorial(int x)
{
if (x < 2) return 1;
return x * Factorial(x - 1);
}
private static void PrintArray(int[] array)
{
string s = "";
for (int i =0; i
s += array[i] + ", ";
}
Console.WriteLine(s + array[array.Length - 1]);
}
private static int[] GenRandomArray(int length)
{
int[] array = new int[length];
for (int i = 0; i < length; i++)
{
array[i] = rnd.Next(10*length);
}
return array;
}
private static bool Sorted(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
compctr++;
if (array[i] < array[i - 1]) return false;
}
return true;
}
private static int[] Shuffle(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int pos = rnd.Next(array.Length);
int temp = array[pos];
array[pos] = array[i];
array[i] = temp;
}
return array;
}
}
}
For a far better reading experience see the Algorithm wiki page on bogosort.
