Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bogo-bogosort

dangermouse.net

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Bogo-bogosort

#21

Post by gcr »

fragsworth wrote: post #13
mikeash wrote: post #11

This got me thinking about a more generalized approach to this sort of thing. Given a task where you can check completion somehow , you can then solve it using the following procedure: 1. Generate a random program. (This could be a Turing machine, bytecode, C source, whatever.) 2. Execute the program on the input for n steps, where n is an incrementing counter. 3. Execute the given check on the output. If the check p…

We both came up with nearly the same idea at nearly the same time (within one minute) - what are the odds of that? My solution is slightly different - to avoid the Halting Problem, you can use a distributed approach. You have a very large (but finite) number of processors that you pass your programs to.

Why not just pass it to an infinite number of processors and use a nondeterministic Turing machine?

But with an NDTM, even NP-complete problems can be solved within polynomial time.

Re: Bogo-bogosort

#22

Post by thetwiceler »

duncanwest wrote: post #4

You 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.

The mean would certainly be n! (note that it is possible, and even likely, that you may create the same sorting multiple times by random chance).

The median, which I don't think you're referring to, is something else (I imagine it would be substantially less than the mean).

(See http://en.wikipedia.org/wiki/Geometric_distribution)

Re: Bogo-bogosort

#23

Post by egypturnash »

eridius wrote: post #7

This 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…

I think half the point of this is the straight-faced, detailed examination of exactly how terrible this proposed sort is.

Or at least that's the part that made me start giggling...

Re: Bogo-bogosort

#25

Post by elwell »

eridius wrote: post #7

This 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…

If all you have is a hammer, everything looks like a nail. It's for this reason that computer scientists created bogobogosort (and sleepybogosort, as you mentioned). For example, bogobogosort tests memory cards more efficiently than a smaller-space algorithm like bogosort. In this case, the recursive nature of bogobogosort acts as space multiplier and fully fills the memory cards (be it DIMM or others). Don't be so quick to judge an algorithm just because it's new.

Also, I'm working on a Bogo programming language with randomized compilation; if anyone is interested in contributing, let me know.

Re: Bogo-bogosort

#26

Post by elwell »

mikeash wrote: post #14
fragsworth wrote: post #13

Earlier quoted context omitted.

We both came up with nearly the same idea at nearly the same time (within one minute) - what are the odds of that? My solution is slightly different - to avoid the Halting Problem, you can use a distributed approach. You have a very large (but finite) number of processors that you pass your programs to.

"what are the odds of that?" I'm not sure, maybe we should build an unbelievably inefficient program to calculate them.

But is it really inefficient if it is efficient at being inefficient?

Re: Bogo-bogosort

#28

Post by ChristianMarks »

I have a soft spot in my head for turdsort, which attempts to optimize over bogosort, but ends up being no better.

  #!/usr/bin/python
  from random import shuffle

  def turdsort(a):
    def turds(a):
      n = 0
      for i in xrange(len(a)-1):
        if a[i] > a[i+1]:
          n += 1
      return n

    count = 1
    n = len(a)
    t = turds(a)
    while n > 0:
      while t >= n:
        shuffle(a)
        t = turds(a)
        count += 1
      n = t
    return count

  if __name__ == '__main__':
    a = range(10)
    print a
    print turdsort(a)
    shuffle(a)
    print a
    print turdsort(a)
Post reply on HN