Truly Awful Algorithms – BogoSort

After covering the semi-awful GnomeSort, I decided to dig into papers on sorting algorithms to see if anyone’s ever published something on a completely awful sort algorithm. This led to BogoSort, first published in 1996 in the New Hacker’s Dictionary and then analysed by Hermann Gruber, Markus Holzer and Oliver Ruepp for some reason at some point later in time.

The basis of bogosort is to randomly swap elements in your array until they become sorted, which required one pass to randomly swap elements and another to verify it was sorted. This give a worst case O time of O(N * N!), though in theory it could run forever. However odds are even with a large number of elements it will eventually finish, after all even if it’s unlikely given enough time you’ll see an end. Even a big bang happens every once and awhile due to randomness.

Here’s a sample of BogoSort written in C#:

    public static class SortAlgorithms
    {
        public static int[] BogoSort(this int[] a)
        {
            if (a.Length < 2)
                return a;

            var rand = new Random();
            var sorted = false;

            while (!sorted)
            {
                for (var i = 0; i < a.Length; i++)
                {
                    var j = rand.Next(0, a.Length);
                    var tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }

                sorted = true;
                for (var i = 1; i < a.Length; i++)
                {
                    if (a[i] < a[i - 1])
                        sorted = false;
                }
            }

            return a;
        }
    }

What’s fun about this algorithm is it’s impossible to tell how long it will truly take to run. For fun I decided to chart out the average number of passes it takes for this algorithm to sort arrays of integers from 3 to 10 elements over 1000 passes each (any larger than 11 and it takes a long time to measure performance):

Advertisement