*Bogosort* can be described as follows:

- Check if your list of number is sorted. If so, stop. If not, go to step 2.
- Rearrange the list of numbers randomly.
- Go to step 1.

This is far too efficient.

Bogobogosort specifies *how* one should check if the list of numbers is sorted. It does it recursively,
because as anyone who knows anything at all about computer science knows, recursion is always good and cool.
To check if the list is sorted, use the following procedure:

- Make a copy of the list of numbers.
- Sort the first
*n*-1 elements of the copy using bogobogosort. - Check to see if the
*n*th element of the sorted copy is greater than the highest element of the first*n*-1 elements. If so, the copy is now sorted, else randomise the order of the elements of the copy and go to step 2. - Check to see if the copy is in the same order as the original list.

Bogobogosort was implemented in C++ and timing runs made for sorting *n* numbers, averaged over 20 trials:

n | Time (seconds) |
---|---|

1 | 0.0000 |

2 | 0.0000 |

3 | 0.0008 |

4 | 0.0054 |

5 | 0.0745 |

6 | 450 |

7 | run overnight, did not finish |

Mike Rosulek writes:

I believe bogobogosort is O(Nathan Collins, on the other hand, writes:n* (n!)^{n}).Let BBS(

n) be the expected time of bogobogosort on input sizen, and SC(n) the expected time of the sort checking algorithm on input sizen. ThenBBS(Then substituting in for SC (skipping some simplifications - the (1-1/n) = SC(n) + (1 - 1/n!) BBS(n)

// with probability 1/n!, we finish, otherwise repeat BBS(n)

SC(n) = O(n) + BBS(n-1) + (1-1/n)( BBS(n-1) + O(n) )

// with probability 1/n, then-th guy is the largest, otherwise must shuffle and re-sort the firstn-1 guysn)*O(n) factor gets swallowed by the first O(n)):BBS(n) = O(n) + BBS(n-1) + (1-1/n) BBS(n-1) + (1-1/n!) BBS(n)

// multiply byn!

n! * BBS(n) = O(n*n!) +n! ( BBS(n) + 2 BBS(n-1) ) - BBS(n) - (n-1)!*BBS(n-1)

// rearrange

BBS(n) = O(n*n!) + (2n! - (n-1)!)BBS(n-1)

= O(n*n!) + O(n!) * BBS(n-1)

= O(n*n!) + O(n*(n!)^{2}) + ... + O(n*(n!)^{n})

= O(n*(n!)^{n})

Let B(n) be the time complexity of bogobogosort on an input of sizen. From the original analysis of bogosort we expect to tryn! times before the random shuffle sorts the list. So,B(Making a copy of the list is O(n) ≤n!*(Copy(n) + Check(n) + Randomize(n))n) (assuming the size of the numbers is bounded). To randomize, you can drop all the numbers on the floor. Dropping them is O(1), and it takes O(n) to pick them up and put them back in the computer (assuming you only have O(1) many hands).To check if the original list is sorted we need to bogobogosort the first

n-1 elements of the copy, and then see if the last element of the copy is at least as large as then-1st. If thenth element of the copy isn't maximal we need to randomize the copy again. And, finally, when we have managed to sort the copy, we need to compare it to the original list. So, since the chance that the last element is maximal is at least 1/n, we have:Check(givingn) ≤n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)B(Comparing the twon) ≤n!*(Copy(n) + (n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)) + Randomize(n))n-element lists is O(n), so we haveB(using O(n) ≤n!*(O(n) + (n*(B(n-1) + O(1) + O(n)) + O(n)) + O(n))

=n!*(O(n) +n*(B(n-1) + O(n)))

=n!*(n*(B(n-1) + O(1) + O(n))

=n!*(n*(B(n-1) +n*O(1)))n) =n*O(1) and O(1) + O(n) = O(n). Expanding B(n-1) recursively we getB(Now, the constant O(1) is the same for all terms above, and then) =n!*n^{2}*O(1) +n!*n^{2}*(n-1)!*(n-1)^{2}*O(1)

+n!*n^{2}*(n-1)!*(n-1)^{2}*(n-2)!*(n-2)^{2}*O(1) + ...

+n!*n^{2}*(n-1)!*(n-1)^{2}*(n-2)!*(n-2)^{2}*...*2!2^{2}*1!*1^{2}*O(1)nth term bounds the firstn-1 terms. So, replacing with the last term throughout, we getB(by folding the square terms and the leading n into the smaller factorials, and absorbing a 2 into the constant. Son) ≤n*n!*n^{2}*(n-1)!*(n-1)^{2}*(n-2)!*(n-2)^{2}*...*2!2^{2}*1!*1^{2}*O(1)

=n!*n!*n!*n!*(n-2)!*(n-3)!*...*4!*3!*O(1)B(wheren) = O(n!*n!*n!*n!*(n-2)!*(n-3)!*...*(k+1)!)kis any fixed number and we have absorbed factorials less than (k+1)! into the constant. Noting that we could bound each (n-j)! byn! we can simplify the bound to B(n) = O(n!^{n-k}), for any fixedk.Now O(

n!^{n-k}) is much better than your guess of O(n!^{n!}), making bogobogosort even more attractive.

Home | Esoteric Programming Languages

Copyright © 1990-2015, David Morgan-Mar.