pikamonstruosa's blog

By pikamonstruosa, history, 7 months ago, In English

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.

Code

*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.

Code

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)

Code

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:

  1. Check if the array is sorted
  2. Have faith
  3. Check if, by some miracle, the array is sorted again
code

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.

  • Vote: I like it
  • +97
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Reminds me of this. And it's actually O(Faith^-1).

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Part 2 when?

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I laughed so hard to this

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fun fact, on recent Serbian contest there was a problem where bogo sort is actually useful assuming you don't know how to sort the array.

»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

You missed Java sort. It literally gets hacked on any 12 hour hacking phase.