Bogosort : Moving At The Pace of a Random Snail

Bogosort is a sorting algorithm, much like quick sort, and merge sort, with a twist.
It has an average case performance of O((n+1)!).

Bogosort is known by many other names, including stupid sort, monkey sort, and permutation sort.

Knowing this critical information, let’s dive into the meat of this sorting algorithm.

How Does It Work?


Bogosort works by taking an input list, and checking if it is in order. If it is, then we are done, and the list is returned. This means that Bogosort has a best case performance of O(n).

If the list isn’t in order, then we will shuffle the list until we get a list that is sorted. Unfortunately, since the list will be shuffled randomly, Bogosort technically has a worst case performance of O(∞).

 

Implementation


Bogosort’s implementation is short and concise.

import random

def Bogosort(list):
    while not isSorted(list):
        random.shuffle(list)
    return list

def isSorted(list):
    if(len(list) <= 1):
        return True

    if(list[1] >= list[0]):
        return isSorted(list[1:])
    else:
        return False

Simple and crisp. Let’s try it on some inputs.
Note that I used Python’s time module to print out the time, which is quick and dirty, but it does the job.

Bogosort([5,4,3,2,1])
Time = 0.000202894210815

Okay. Now let’s try it again on an input size of 10.

Bogosort([10,9,8,7,6,5,4,3,2,1])
52.8398268223

Since it is completely randomized, running this will give different times each time it is run, but the ballpark figure will at least be somewhat similar.

Normally, I’d try on a larger input size, but since the growth rate is going to be exponential, an input size of 11 will cause a time that is much longer than when an input size of 10 is used.

In fact, in our example, running on an input size of 10 took over 260,000 times longer than when run on an input size of 5.

However, since the numbers are random, it is impossible to determine exactly how much longer it will take , but it should be somewhere around that range.

Conclusion


If you are looking for a horrendously slow sorting algorithm for any reason, Bogosort is the perfect candidate. It works by randomly shuffling the list until it gets a sorted list, which means that its average performance is going to be O((n+1)!).

Of course, Bogosort should not be taken as a serious sorting algorithm, and is intended to be used as a comparison to other sorting algorithms like quick sort and merge sort.

Unless your goal is to create slow code, stay far far away from this monstrosity.

 

Java Lambdas : Syntactic Sugar

You glance down at your list of invited guests for your party.
Suddenly, you see someone with the last name of “Dang”, the very same family that ruined your party the last time they showed up.

Furiously, you write a program to sort through the hundreds of invited guests to remove everyone with the last name “Dang”.

For the sake of simplicity, a smaller list will be used, but nonetheless, you end up with this hideous snippet:

public class Party {

    static List invitedGuests;

    public static void main(String[] args){

        invitedGuests = new ArrayList() {{
	    add("Henry Dang");
            add("Joe Dang");
	    add("Kevin Smith");
	    add("John Dang");
	    add("John Doe");
	    add("Michelle Sans");
        }};

	for(Iterator iterator = invitedGuests.iterator(); iterator.hasNext();){
            String guestName = iterator.next();

	    if(guestName.contains("Dang")){
                iterator.remove();
	    }
	}

	for(String guests : invitedGuests){
	    System.out.println(guests);
	}
    }
}

 

What a terribly cluttered mess!

But what if you could have done it in a simpler, more concise way?
With Java 8’s lambdas, you can cut down the length of the logic to 1/5th of its size!

public class Party {

    static List invitedGuests;

    public static void main(String[] args){

        invitedGuests = new ArrayList() {{
	    add("Henry Dang");
            add("Joe Dang");
	    add("Kevin Smith");
	    add("John Dang");
	    add("John Doe");
	    add("Michelle Sans");
        }};

     invitedGuests.removeIf(name -> name.contains("Dang"));
     invitedGuests.forEach(name -> System.out.println(name));
    }
}

Just like that, your code instantly becomes clean, concise, and expressive.
The removeIf method simply takes a Predicate, which is basically a boolean. It checks if the name contains the word “Dang” in it, and if it does, it instantly removes it from the list.

The line after it is just a fancy for each loop, except it’s only one line long. The forEach method takes in a Consumer object, which basically says, “Give me a parameter, and something to do with that parameter.” You pass in the parameter “name”, and print all the names in the list.

Now that you’re done, all the Dangs are off your list, and you’ve shortened your otherwise obnoxiously verbose code by 8 lines.