With the broad availability of quick and efficient sorting algorithms, that can sort arrays in $$$O(N*logN)$$$ complexity, little attention has been given to the vast and interesting world of the bad sorting algorithms. Because of this, I will, in this blog, explore this area. To make this list more interesting, we are only going to consider the algorithms in which play a role in the sorting process. That is, there won't be algorithms that use a wait function or an infinite loop.
Bogosort
-This may be the most famous bad sorting algorithm. Its legendary strategy consists of randomly shuffling and array until it is sorted.
*It is also worth mentioning that there is a variant of this algorithms that eliminates the randomness issue: Create all $$$N!$$$ possible permutations of a given array. Go through each one checking if they are ordered or not.
Complexity
- In average, $$$(N-1)*N!$$$ swaps are made.
Bozosort
-This is another sorting algorithm that relies on randomness to be bad and the strategy it uses to sort is quite simple: If the array is not ordered, randomly select two elements of an array, swap them. The expected time complexity is a bit more complex, but on average $$$N!$$$ swaps are made.
Slowsort
-This algorithm is a very interesting one. It utilizes the infamous technique of multiply and surrender in order to sort its elements. The recursion it utilizes is very "efficient" and interesting:
function slowsort(begin,end)
mid = floor((begin + end)/2)
slowsort(begin,mid)
slowsort(mid + 1, end)
if(array[mid] > array[end]) swap(array[mid],array[end]) //we compare the greatest element of each half
//now, the greatest element of the array is in the end, so we call recursively without including the last element
slowsort(begin,end - 1)
Complexity
- The complexity of this method is kinda sketchy, so I will just say it is very very bad (not polynomial, not by far).
To finish this amazing list, I will present a sorting algorithm that becomes faster the more faith one has. I present to you the unmatched, the most amazing:
Miracle Sort
This niche method relies solely on the faith the programmer has on whatever it is that he believes. The method to sort consists of 3 simple steps:
- Check if the array is sorted
- Have faith
- Check if, by some miracle, the array is sorted again
With this quite reliable method, one can hope that the array will be sorted in $$$O(Faith^{-1})$$$ time complexity.
Conclusion
I hope you enjoyed this trip through the bad sorting algorithms. This is merely an introduction and I have yet to see everything bad algorithms have to offer. I find them interesting because the way they manage to get such a bad complexity is quite creative.