Bogosort is adorable, when he isn't running away.  

The two-year-old son of Heap Sort and Cocktail Shaker Sort, he is possibly the most mischievous scamp this side of the Mississippi, or at least that's what his grandfather would say.  

picking flowers
"Who, me?" Photo by Luke Brugger / Unsplash

A favorite trick of his happens when the family plays poker, or Uno, or any other game involving cards. He sneaks up to the table (he can be very quite when he wants to be) and runs off with as many cards as his little hands can grab.  As you might imagine, this dramatically improves the game, at least in his tiny opinion. The adults who have to spend time chasing him down, vaulting over dogs and rounding corners at dangerously high speeds, might disagree.

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound

Algorithm

  1. IF the list is not sorted...
  2. SHUFFLE the list randomly
  3. GO TO 1, CONTINUE until list is sorted.

Visualization

Lily, Rosemary, and the Ace of Spades
Photo by Jack Hamilton / Unsplash

A visualization for this particular sorting algorithm is kind of ridiculous. The procedure is just "shuffle randomly until sorted", very much like taking a deck of cards, throwing them into the air, gathering them up, and repeating this until the deck is in the correct order.

If you think this algorithm is amazingly stupid, you are not wrong.

But it's not the slowest algorithm ever. That honor goes to Bogobogosort, an algorithm that was specifically designed to be as slow as possible while still doing a ton of work. The author's own guess on that algorithm's time complexity is O(n!n!). That's just crazy.

That said, the "audibilization" of Bogosort is pretty neat: a ton of noise for not very much gain:

C# Implementation

class BogoSort
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>() { 2, 1, 3, 0 };
        Console.WriteLine("BogoSort");
        Console.WriteLine("Sorting...");
        Sort(list);
        Console.WriteLine("Press any key to exit.");
        Console.ReadKey();
    }

    static void Sort(List<int> list)
    {
        int iteration = 0;
        while (!IsSorted(list))
        {
            PrintIteration(list, iteration);
            list = Shuffle(list); //Shuffle the numbers randomly
            iteration++;
        }

        PrintIteration(list, iteration); //Print the final, sorted iteration
        Console.WriteLine();
        Console.WriteLine("BogoSort completed after {0} iterations.", iteration);
    }

    static void PrintIteration(List<int> list, int iteration)
    {
        Console.Write("BogoSort iteration #{0}: ", iteration);
        foreach(var value in list)
        {
            Console.Write($"{value} ");
        }
        Console.WriteLine();
    }
    static bool IsSorted(List<int> list)
    {
        for (int i = 0; i < list.Count - 1; i++)
        {
            if (list[i] > list[i + 1])
            {
                return false;
            }
        }

        return true;
    }

    //Shuffle algorithm based on Fisher-Yates method.
    static List<int> Shuffle(List<int> numbers)
    {
        Random r = new Random();
        //Step 1: For each unshuffled item in the collection
        for (int n = numbers.Count - 1; n > 0; --n)
        {
            //Step 2: Randomly pick an item which has not been shuffled
            int k = r.Next(n + 1);

            //Step 3: Swap the selected item 
            //        with the last "unstruck" item in the collection
            int temp = numbers[n];
            numbers[n] = numbers[k];
            numbers[k] = temp;
        }
        return numbers;
    }
}

Time and Space Complexity

Any time you see a factorial (!) in a math equation, and you want that number to be small, you're gonna have a bad time.

The average-case for Bogosort is O((n + 1)!). This means that, as the size of the collection increases, the time the algorithm requires to shuffle the collection increases dramatically. There's a reason why the implementation above has only four numbers in the starting collection; any more and I was getting hundreds of permutations before finding a solution (if one was found at all).

Summary

Obviously, Bogosort isn't meant to be taken seriously as a sorting algorithm. It's not useful in the real world; the algorithm can be reduced to "shuffle until sorted" which might take forever. That said, it can be useful, in a "do not do this" kind of way. Just make sure he can't reach the cards.

Bogosort's older sister, Bubble Sort, is next up, and you better have some earmuffs handy.

Bubble Sort in C#
The indefatigable Bubble Sort is beloved by her whole family, provided she isn’tin the room. The eight-year-old daughter of Heap Sort and Cocktail Shaker Sort, sheabsolutely loves to tell you all about her day: what things she ate, this coolcar she saw on the way over, how her little brother is …
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!