Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

[Tutorial] An introductory guide to the worst sorting algorithms

Revision en11, by pikamonstruosa, 2023-12-05 17:38:37

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English pikamonstruosa 2023-12-05 17:38:37 0 (published)
en10 English pikamonstruosa 2023-12-05 17:09:03 274
en9 English pikamonstruosa 2023-12-05 16:47:14 92
en8 English pikamonstruosa 2023-12-05 16:42:45 890
en7 English pikamonstruosa 2023-12-05 16:19:08 11
en6 English pikamonstruosa 2023-12-05 16:11:49 1214 Tiny change: 'ted in $O(N^(Faith))$ time co' -> 'ted in $O(Faith^-1)$ time co'
en5 English pikamonstruosa 2023-07-15 18:02:55 1229
en4 English pikamonstruosa 2023-07-15 17:52:15 150
en3 English pikamonstruosa 2023-07-15 17:12:42 1601
en2 English pikamonstruosa 2023-07-14 19:59:56 227 Tiny change: 's.\n\n### ### ### Bogoso' -> 's.\n\n### Bogoso'
en1 English pikamonstruosa 2023-07-14 04:30:51 266 Initial revision (saved to drafts)