The life of coronavirus lockdown is weird, it is a life we have never experienced before.
Everything seems slow down, even shutdown.
As software engineers, we have always wanted to make our program run faster. On these unexperienced days, let us try to think about something from the opposite angle.
Do you know what is the slowest sorting algorithm?
Let’s have some fun and learn some unusual time complexity analysis.
Bogosort (a.k.a Monkey sort)
Bogosort is based on the generate and test paradigm.
Let’s implement this algorithm in Python:
Average time complexity is O((N-1)* N!), the best case occurs if the given array is already sorted.
You may think the worst-case needs infinite time.
It’s right in theory.
Actually, for any array with a fixed size, the expected running time of the algorithm is finite. This is because infinite monkey theorem holds in practice.
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare.
– From Wikipedia
If we give enough time, bogosort sort will almost surely sort the array.
So, bogosort is also called Monkeysort.
Another variant is Bozosort, which only swap two elements until we get a sorted result. The runtime complexity of Bozosort is also O(N!).
Could we sort an array without any comparison?
Yes, it’s possible!
Sleep sort is originally posted by anonymous user posted on 4Chan:
To implement it in Python, we spawning off one thread for each element of the array, and each thread wait for v seconds to start, where v is the value of an element:
The time complexity is O(Max(array)), very time consuming on performance!
Slow sort is a tongue-in-cheek joke of divide and conquer. It’s a recursive algorithm and seems similar to quicksort.
On the contrary, it’s extremely slow.
Could you figure out the time complexity of this algorithm? Honestly, I can not :).
According to Wikipedia, even the best case is worse than Bubble sort.
This video is a visualization of how it works:
Although these sorting algorithms are actually not useful, they are interesting.
I hope you like it and have a smile. Stay well.