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):

Truly Awful Algorithms – Gnome Sort

During my pursuit to learn about new algorithms I came across one with a funny name, and a simple implementation, and is generally just awful to use in any real world case. So here we have Gnome Sort. Proposed by Hamid Sarbazi-Azad in 2000, this algorithm’s best feature is the existence of a single while to do all the sorting. Here’s an implementation of it in C# as an extension to an array of integers*:

public static class SortAlgorithms
    {
        public static int[] GnomeSort(this int[] a)
        {
            if (a.Length <= 1)
                return a;

            var i = 1;
            while (i < a.Length)             {
                if (a[i] >= a[i - 1])
                    i++;
                else
                {
                    var tmp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = tmp;
                    if (i > 1)
                        i--;
                }
            }
            return a;
        }
    }

If you will, imagine you asked your garden gnome to sort your flower pots based on size, how would he go about it? Why he would walk down the line of flower pots and look at the one he was next to and the one behind it, and if the one he’s next to is small than the other one he’d swap them and continue to swap it backwards down the line until he no longer finds the pot he’s moving is smaller than the one before it. Then he just starts walking down the line again looking at pots. The best case for this sort is O(N) for an already sorted list, with O(N²) worst case time for a reverse sorted list. The alternative name for this sort is Stupid Sort, not because of the algorithm itself, but because gnomes are stupid and take the most direct approach to solving problems. On the plus side you only had to spend one loop!

* Consider this code MIT Licensed if for some insane reason you want to use it