License Creative Commons Attribution Share Alike 3.0-US
Keywords
bogo (1) bogosort (5) joke (1) sort (5)
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Free your code from a slow death on your hard drive Join Siafoo Now or Learn More

BogoSort Atom Feed 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 if
10
11 // If array is not sorted, randomize it and try again!
12 array = randomize_array(array)
13
14 while is_sorted == False
15
16 end function
17
18
19 function randomize_array(array)
20
21 n = length(array)
22
23 for i = 1 to i = n-1
24
25 // Get a random array position after "i"
26 j = random_integer(i...n)
27
28 //Swap the values at the two positions
29 swap(array[i] and array[j])
30
31 end for
32
33 return array
34
35 end function
36
37
38 function check_whether_sorted(array)
39
40 n = length(array)
41
42 for i = 1 to i = n-1
43
44 // If any two consecutive values are out of order
45 // then the array is not sorted.
46 if array[i] > array[i + 1]
47 return False
48 end if
49
50 end for
51
52 // If nothing was out of order, the array is sorted.
53 return True
54
55 end function
56
Flow Graph

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++....
Real code trolling :D, note the generator expression combined with built in function any(), it will return after the first miss match.
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...

Comments

over 5 years ago (31 Jul 2008 at 01:40 PM) by Stou S.
Wow... I'd like to see the performance bound this thing.
over 5 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 5 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 5 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 5 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 5 years ago (03 Aug 2008 at 06:23 PM) by Theodore Test
Oh, handy graph Stou.
over 5 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 5 years ago (04 Aug 2008 at 06:53 AM) by Theodore Test
How about like this...

.. image:: 66
:alt: Bogosort Flowchart
:width: 500
:height: 500
over 5 years ago (04 Aug 2008 at 06:53 AM) by Theodore Test
Hmm, I guess no reST in comments. Sigh.
over 5 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 5 years ago (22 Mar 2009 at 02:34 PM) by David Isaacson
Someone really needs to implement this in Brainfuck!
over 4 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 4 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 4 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.