##### Keywords
bogo (1) bogosort (5) joke (1) sort (5)
##### Permissions
Viewable by Everyone
Editable by All Siafoo Users

# BogoSort 6

 In Brief BogoSort is a highly ineffective algorithm notable only for its comedic value.... more
 Implementation Difficulty
` 1 function bogo_sort(array) 2  3     do 4         is_sorted = check_whether_sorted(array)     5  6             // If the array is sorted, we're done. 7             if is_sorted == True 8                 return array 9             end if10 11         // If array is not sorted, randomize it and try again!12         array = randomize_array(array)13 14     while is_sorted == False15 16     end function17 18 19 function randomize_array(array)20 21     n = length(array)22 23     for i = 1 to i = n-124 25         // Get a random array position after "i"26         j = random_integer(i...n)27 28           //Swap the values at the two positions29         swap(array[i] and array[j])30 31     end for32 33     return array34 35     end function36 37 38 function check_whether_sorted(array)39 40     n = length(array)41 42     for i = 1 to i = n-143 44         // If any two consecutive values are out of order45         // then the array is not sorted.46         if array[i] > array[i + 1]47             return False48         end if49 50     end for51 52     // If nothing was out of order, the array is sorted.53     return True54 55     end function56     `

BogoSort is a highly ineffective algorithm notable only for its comedic value.

The primary loop checks whether the input array is properly sorted and randomizes the entire array if it is not.

An analogy would be painting numbers on goldfish in a pond, counting the order in which the fish cross under a bridge, and dropping a grenade into the water whenever don't happen to like that order.In other words, you'd have to be crazy to implement this algorithm. Mathematically, the worst case scenario is that the algorithm takes an infinite amount of time to resolve. Even looking at "average case" values, the expected number of swaps is and the expected number of value-comparisons is .

Implementations
The standard library algorithm random_shuffle makes for an easy implementation of BogoSort in C++....
+1
Real code trolling :D, note the generator expression combined with built in function any(), it will return after the first miss match.
+1
An implementation of the sweet BogoSort algorithm. Just download, run, and enjoy....
Just for fun. Only time I'd recommend using it is if you're trying to convince someone it's time to upgrade a box. :o...
Only as ridiculously inefficient as it needs to be.
A NumPy-based implementation of the ever-hilarious Bogosort algorithm. Tries (hopelessly) to optimize the algorithm by taking advantage of lazy iterators, NumPy C-based shuffling, and minimizing...
In Javascript, you can pass a function to the Array.sort method, and tell that function to just return whatever the hell it wants. This makes for an easy, but very slow (suprise!) Bogosort...

over 11 years ago (31 Jul 2008 at 01:40 PM) by Stou S.
Wow... I'd like to see the performance bound this thing.
over 11 years ago (31 Jul 2008 at 02:07 PM) by Theodore Test
Technically, the worst-case run time is infinite, on account of the probabilistic nature of the randomization subfunction.
over 11 years ago (31 Jul 2008 at 02:07 PM) by Theodore Test
However, the expected numbers for the algorithm running parameters are finite.

The average-case number of swaps asymptotes towards (n-1)*n! and the average-case number of comparisons approaches (e-1)*n! + O(1)
over 11 years ago (31 Jul 2008 at 02:46 PM) by Andrew Stromberg
I was messing around and put in a 17 number array for this algorithm, I guess I have better odds of winning the powerball.
over 11 years ago (31 Jul 2008 at 02:58 PM) by Stou S.
It only took 5 minutes for my 11 number array. I think a chart is in order.

We should form a club, with the purpose of wasting CPU time sorting things with BogoSort and attempting to get BogoSort into database servers and numerical libraries.
over 11 years ago (03 Aug 2008 at 06:23 PM) by Theodore Test
Oh, handy graph Stou.
over 11 years ago (03 Aug 2008 at 07:21 PM) by Stou S.
Thanks. Too bad I couldn't get the 'Shuffle Array' and 'Is Sorted' nodes to be side by side (after an hour of trying). Also discovered (and fixed) a bug in the way algorithm editing works :-/
over 11 years ago (04 Aug 2008 at 06:53 AM) by Theodore Test

.. image:: 66
:alt: Bogosort Flowchart
:width: 500
:height: 500
over 11 years ago (04 Aug 2008 at 06:53 AM) by Theodore Test
Hmm, I guess no reST in comments. Sigh.
over 11 years ago (04 Aug 2008 at 09:41 AM) by David Isaacson
Yeah... that is something we keep meaning to implement... and then not actually doing it ;-)
over 10 years ago (22 Mar 2009 at 02:34 PM) by David Isaacson
Someone really needs to implement this in Brainfuck!
over 10 years ago (17 Jun 2009 at 09:14 AM) by fbinder
I wonder what would happen if this algorithm was implemented in the "Hitchhiker´s Guide to the Galaxy" series. Maybe it would be the fastest of all...
updated over 10 years ago (17 Jun 2009 at 02:00 PM) by Stou S.
I am pretty sure Cosmic Ray Sort will take the cake in the Hitchhiker's guide ( http://www.siafoo.net/algorithm/9 )
over 10 years ago (05 Aug 2009 at 05:04 AM) by rwebler
Cosmic Ray Sorting would have a chance to succeed when the Infinite Improbability Drive is used.