Bogo-bogosort
dangermouse.net
Bogo-bogosort
1–10 of 33 posts
Re: Bogo-bogosort
#2My favorite line: "as anyone who knows anything at all about computer science knows, recursion is always good and cool."
Re: Bogo-bogosort
#3My addition to the algorithm: Every time your check if arrays is sorted and it isn't, start from the very beginning throwing away all progress made so far.
I doubt this way n == 6 would finish in some normal time period.
Re: Bogo-bogosort
#4You say it will take on average n! attempts to find a sorted list randomly. This is false. It will take on average n!/2 attempts.
Re: Bogo-bogosort
#5You say it will take on average n! attempts to find a sorted list randomly. This is false. It will take on average n!/2 attempts.
O(n!/2) == O(n!), the whole paragraph is obviously referring to big o notation.
edit:( I have edited the post to respond to your comment, trying to clarify what OP meant; I in no way tried to make your comment "look silly" )
Re: Bogo-bogosort
#6You say it will take on average n! attempts to find a sorted list randomly. This is false. It will take on average n!/2 attempts.
O(n!/2) == O(n!), the whole paragraph is obviously referring to big o notation. edit:( I have edited the post to respond to your comment, trying to clarify what OP meant; I in no way tried to make your comment "look silly" )
Yes, but that's not what he says. He says "The loop will repeat on average n! times". That's not true. He's not referring to O notation there, he brings that in later. Here he's talking about the imperative number of times a loop will run on average.
Edit: you've edited your paragraph to make my reply look silly. The whole paragraph is not in O notation. In fact - the exact opposite. In the last sentence of that paragraph he shows what the expression with constant factors looks like before converting it into O notation, and it's wrong! "The product (n-1)n! is O(n × n!)." Bzzzzzzt! Wrong! He should say "The product (n-1)(n!/2) is O(n × n!)."
Re: Bogo-bogosort
#7This seems completely pointless. The elegance of bogosort is that it's an extremely simple algorithm, with a simple description of "randomize until it's sorted". Bogobogosort is complicated for no apparent reason. It's trying to be cute and clever, but there's no rationale for why additional complexity is being added.
Bogobogosort seems in the end to be no more worthwhile than sleepybogosort, where you must sleep() in between every operation.
Re: Bogo-bogosort
#8This seems completely pointless. The elegance of bogosort is that it's an extremely simple algorithm, with a simple description of "randomize until it's sorted". Bogobogosort is complicated for no apparent reason. It's trying to be cute and clever, but there's no rationale for why additional complexity is being added. Bogobogosort seems in the end to be no more worthwhile than sleepybogosort, where you must sleep() i…
No, since the complexity of bogosort with sleep is still O(n!), while the algorithm from OP has a higher bound.
Re: Bogo-bogosort
#9You say it will take on average n! attempts to find a sorted list randomly. This is false. It will take on average n!/2 attempts.
True, but that's still O(n!), so the overall complexity doesn't change.
Re: Bogo-bogosort
#10My favourite is still Intelligent Design Sort:
http://www.dangermouse.net/esoteric/intelligentdesignsort.ht...
O(1) run time!