Are there any worse sorting algorithms than Bogosort a k a Monkey Sort

Question

My co-workers took me back in time to my University days with a discussion of sorting algorithms this morning   We reminisced about our favorites like StupidSort  and one of us was sure we had seen a sort algorithm that was O n     That got me started looking around for the  worst  sorting algorithms I could find   We postulated that a completely random sort would be pretty bad  i e  randomize the elements - is it in order   no   randomize again   and I looked around and found out that it s apparently called BogoSort  or Monkey Sort  or sometimes just Random Sort   Monkey Sort appears to have a worst case performance of O 8   a best case performance of O n   and an average performance of O n  n     What is the currently official accepted sorting algorithm with the worst average sorting performance  and there fore beeing worse than O n  n

User · Answer

Bozo sort is a related algorithm that checks if the list is sorted and  if not  swaps two items at random  It has the same best and worst case performances  but I would intuitively expect the average case to be longer than Bogosort  It s hard to find  or produce  any data on performance of this algorithm

User · Answer

Bogobogosort  Yes  it s a thing  to Bogobogosort  you Bogosort the first element  Check to see if that one element is sorted  Being one element  it will be  Then you add the second element  and Bogosort those two until it s sorted  Then you add one more element  then Bogosort  Continue adding elements and Bogosorting until you have finally done every element  This was designed never to succeed with any sizable list before the heat death of the universe

User · Answer

The  what would you like it to be   sort   Note the system time  Sort using Quicksort  or anything else reasonably sensible   omitting the very last swap  Note the system time  Calculate the required time  Extended precision arithmetic is a requirement  Wait the required time  Perform the last swap    Not only can it implement any conceivable O x  value short of infinity  the time taken is provably correct  if you can wait that long

User · Answer

This page is a interesting read on the topic  http   home tiac net  cri d cri 2001 badsort html  My personal favorite is Tom Duff s sillysort         The time complexity of this thing is O n  a log n      for some constant a  This is a multiply and surrender    algorithm  one that continues multiplying subproblems    as long as possible until their solution can no longer    be postponed      void sillysort int a    int i  int j           int t  m          for  i  j --j                   m  i j  2                  sillysort a  i  m                   sillysort a  m 1  j                   if a m  gt a j    t a m   a m  a j   a j  t

User · Answer

If you keep the algorithm meaningful in any way  O n   is the worst upper bound you can achieve   Since checking each possibility for a permutations of a set to be sorted will take n  steps  you can t get any worse than that   If you re doing more steps than that then the algorithm has no real useful purpose  Not to mention the following simple sorting algorithm with O infinity    list   someList while  list not sorted       doNothing

User · Answer

There is a sort that s called bogobogosort  First  it checks the first 2 elements  and bogosorts them  Next it checks the first 3  bogosorts them  and so on  Should the list be out of order at any time  it restarts by bogosorting the first 2 again  Regular bogosort has a average complexity of O N    this algorithm has a average complexity of O N 1 2 3    N   Edit  To give you an idea of how large this number is  for 20 elements  this algorithm takes an average of 3 930093 10 158 years well above the proposed heat death of the universe if it happens  of 10 100 years  whereas merge sort takes around  0000004 seconds  bubble sort  0000016 seconds  and bogosort takes 308 years  139 days  19 hours  35 minutes  22 306 seconds  assuming a year is 365 242 days and a computer does 250 000 000 32 bit integer operations per second  Edit2  This algorithm is not as slow as the  quot algorithm quot  miracle sort  which probably  like this sort  will get the computer sucked in the black hole before it successfully sorts 20 elemtnts  but if it did  I would estimate an average  complexity of 2  32 the number of bits in a 32 bit integer  N  the number of elements   a number  lt  10 40  years  since gravity speeds up the chips alpha moving  and there are 2 N states  which is 2 640 10 40  or about 5 783 10 216 762162762 years  though if the list started out sorted  its complexity would only be O N   faster than merge sort  which is only N log N even at the worst case  Edit3  This algorithm is actually slower than miracle sort as the size gets very big  say 1000  since my algorithm would have a run time of 2 83 10 1175546 years  while the miracle sort algorithm would have a run time of 1 156 10 9657 years

User · Answer

There s always the Bogobogosort  Bogoception    It performs Bogosort on increasingly large subsets of the list  and then starts all over again if the list is ever not sorted   for  int n 1  n lt sizeof list     n      while   isInOrder list  0  n         shuffle list  0  n         if   isInOrder list  0  n 1     n 0

User · Answer

Recursive Bogosort  probably still O n    if  list not sorted  list1   first half of list  list 2   second half of list  Recursive bogosort  list1   Recursive bogosort  list2   list   list1   list2 while list not sorted      shuffle list

User · Answer

1 Put your items to be sorted on index cards  2 Throw them into the air on a windy day  a mile from your house   2 Throw them into a bonfire and confirm they are completely destroyed   3 Check your kitchen floor for the correct ordering   4 Repeat if it s not the correct order   Best case scenerio is O 8   Edit above based on astute observation by KennyTM

User · Answer

You should do some research into the exciting field of Pessimal Algorithms and Simplexity Analysis  These authors work on the problem of developing a sort with a pessimal best-case  your bogosort s best case is Omega n   while slowsort  see paper  has a non-polynomial best-case time complexity

User · Answer

Double bogosort  Bogosort twice and compare results  just to be sure it is sorted  if not do it again

User · Answer

Jingle Sort  as described here    You give each value in your list to a different child on Christmas   Children  being awful human beings  will compare the value of their gifts and sort themselves accordingly

User · Answer

Here s 2 sorts I came up with my roommate in college  1  Check the order 2  Maybe a miracle happened  go to 1  and  1  check if it is in order  if not  2  put each element into a packet and bounce it off a distant server back to yourself  Some of those packets will return in a different order  so go to 1

User · Answer

My favorite slow sorting algorithm is the stooge sort   void stooges long  begin  long  end       if   end-begin   lt   1   return     if  begin 0   lt  end -1    swap begin  end-1      if   end-begin   gt  1           int one third    end-begin  3        stooges begin  end-one third         stooges begin one third  end         stooges begin  end-one third            The worst case complexity is O n  log 3    log 1 5      O n 2 7095       Another slow sorting algorithm is actually named slowsort   void slow long  start  long  end       if   end-start   lt   1   return     long  middle   start    end-start  2     slow start  middle      slow middle  end      if  middle -1   gt  end -1    swap middle-1  end-1      slow start  end-1       This one takes O n    log n   in the best case    even slower than stoogesort

User · Answer

I had a lecturer who once suggested generating a random array  checking if it was sorted and then checking if the data was the same as the array to be sorted   Best case O N   first time baby   Worst case O Never

User · Answer

You could make any sort algorithm slower by running your  is it sorted  step randomly  Something like    Create an array of booleans the same size as the array you re sorting  Set them all to false  Run an iteration of bogosort Pick two random elements  If the two elements are sorted in relation to eachother  i  lt  j  amp  amp  array i   lt  array j    mark the indexes of both on the boolean array to true  Overwise  start over  Check if all of the booleans in the array are true  If not  go back to 3  Done

User · Answer

Many years ago  I invented  but never actually implemented  MiracleSort   Start with an array in memory  loop      Check to see whether it s sorted      Yes  We re done      No  Wait a while and check again  end loop   Eventually  alpha particles flipping bits in the memory chips should result in a successful sort   For greater reliability  copy the array to a shielded location  and check potentially sorted arrays against the original   So how do you check the potentially sorted array against the original   You just sort each array and check whether they match   MiracleSort is the obvious algorithm to use for this step   EDIT  Strictly speaking  this is not an algorithm  since it s not guaranteed to terminate  Does  not an algorithm  qualify as  a worse algorithm

User · Answer

Yes  SimpleSort  in theory it runs in O -1  however this is equivalent to O    9999  which is in turn equivalent to O  infin  - 1   which as it happens is also equivalent to O  infin    Here is my sample implementation      element sizes are uneeded  they are assumed    void simplesort  const void  begin  const void  end      for

User · Answer

Randomsubsetsort   Given an array of n elements  choose each element with probability 1 n  randomize these elements  and check if the array is sorted  Repeat until sorted   Expected time is left as an exercise for the reader

User · Answer

Segments of p  Assume p contains all possible finite number combinations  See math stackexchange question   Determine the number of digits needed from the size of the array  Use segments of p places as indexes to determine how to re-order the array  If a segment exceeds the size boundaries for this array  adjust the p decimal offset and start over  Check if the re-ordered array is sorted  If it is woot  else adjust the offset and start over

User · Answer

One I was just working on involves picking two random points  and if they are in the wrong order  reversing the entire subrange between them  I found the algorithm on http   richardhartersworld com cri d cri 2001 badsort html  which  says  that the average case is  is probably somewhere around O n 3  or O n 2 log n   he s not really sure    I think it might be possible to do it more efficiently  because I think it might be possible to do the reversal operation in O 1  time   Actually  I just realized that doing that would make the whole thing I say maybe because I just realized that the data structure I had in mind would put accessing the random elements at O log n  and determining if it needs reversing at O n

User · Answer

Quantum Bogosort  A sorting algorithm that assumes that the many-worlds interpretation of quantum mechanics is correct    Check that the list is sorted  If not  destroy the universe    At the conclusion of the algorithm  the list will be sorted in the only universe left standing  This algorithm takes worst-case O N  and average-case O 1  time  In fact  the average number of comparisons performed is 2  there s a 50  chance that the universe will be destroyed on the second element  a 25  chance that it ll be destroyed on the third  and so on

User · Answer

I m surprised no one has mentioned sleepsort yet    Or haven t I noticed it  Anyway      bin bash function f         sleep   1      echo   1    while   -n   1    do     f   1   amp      shift done wait   example usage     sleepsort sh 5 3 6 3 6 3 1 4 7   sleepsort sh 8864569 7   In terms of performance it is terrible  especially the second example   Waiting almost 3 5 months to sort 2 numbers is kinda bad

User · Answer

Nothing can be worse than infinity

User · Answer

From David Morgan-Mar s Esoteric Algorithms page  Intelligent Design Sort     Introduction      Intelligent design sort is a sorting algorithm based on the theory of   intelligent design       Algorithm Description      The probability of the original input list being in the exact order   it s in is 1  n    There is such a small likelihood of this that it s   clearly absurd to say that this happened by chance  so it must have   been consciously put in that order by an intelligent Sorter  Therefore   it s safe to assume that it s already optimally Sorted in some way   that transcends our na  ve mortal understanding of  ascending order     Any attempt to change that order to conform to our own preconceptions   would actually make it less sorted       Analysis      This algorithm is constant in time  and sorts the list in-place    requiring no additional memory at all  In fact  it doesn t even   require any of that suspicious technological computer stuff  Praise   the Sorter       Feedback      Gary Rogers writes            Making the sort constant in time     denies the power of The Sorter  The     Sorter exists outside of time  thus     the sort is timeless  To require time     to validate the sort dimishes the role     of the Sorter  Thus    this particular     sort is flawed  and can not be     attributed to  The Sorter           Heresy

User · Answer

A worst case performance of O 8  might not even make it an algorithm according to some   An algorithm is just a series of steps and you can always do worse by tweaking it a little bit to get the desired output in more steps than it was previously taking  One could purposely put the knowledge of the number of steps taken into the algorithm and make it terminate and produce the correct output only after X number of steps have been done  That X could very well be of the order of O n2  or O nn   or whatever the algorithm desired to do  That would effectively increase its best-case as well as average case bounds   But your worst-case scenario cannot be topped

[algorithm] Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)?

Examples related to algorithm

Examples related to sorting

Examples related to big-o