4 ms·

I've implemented bogosort, though only for illustration purposes (honestly...). Drawing a graph comparing running times of two or three algorithms as the size o

by ranko 11y ago

I've implemented bogosort, though only for illustration purposes (honestly...). Drawing a graph comparing running times of two or three algorithms as the size of the input increases is quite instructive, especially once you see that bogosort goes off the scale (whatever linear scale you use) pretty quickly. To be pedantic (and why not), I don't think that the procedures described in the paper strictly qualify as algorithms because there's no guarantee of termination. That's part of the fun, of course.

JadeNB 11y ago
> To be pedantic (and why not), I don't think that the procedures described in the paper strictly qualify as algorithms because there's no guarantee of termination. I don't think that's part of the description of 'algorithm' (although I don't know if the word has a technical definition, so that we may be left arguing about how we use the word personally). Otherwise, there could be no algorithm for listing all the natural numbers, for example.
- stevetrewick 11y ago
  IIRC the formal definition is something like (but probably not) : any finite set of steps that can be represented by a Turing (complete?) machine. I have seen definitions both with and without the requirement for a halting state. Fortunately someone will be along shortly to explain it properly.
  - JadeNB 11y ago
    However, the existence of a halting state does not imply that all execution paths eventually reach it. Certainly I have never seen a definition (of an algorithm, rather than, say, a total language) that builds in that requirement; otherwise, what would be the objects considered in the halting problem? By this definition, they couldn't just be algorithms, or else "RETURN TRUE" would be a correct decision procedure.
mikeash 11y ago
That's an interesting point about randomness. You could implement a bogo-ish sort that's fully deterministic. Instead of randomly shuffling, iterate through all possible permutations of the input. Assuming the input contains no duplicates, there are n! permutations and one which is sorted, so your average running time will be n n!/2, which matches bogosort. Of course, in this age of cloud computing, we really should be using more modern terrible sorting techniques such as stacksort: https://gkoberger.github.io/stacksort/ https://gkoberger.github.io/stacksort/
cookingrobot 11y ago
That's technically called a "Las Vegas algorithm", because the answer is guaranteed correct, but the runtime has no guarantees. This is in contrast to "Monte Carlo algorithms" where the runtime is bounded, but the answer isn't necessarily correct.

by ranko 11y ago

JadeNB 11y ago

> To be pedantic (and why not), I don't think that the procedures described in the paper strictly qualify as algorithms because there's no guarantee of termination. I don't think that's part of the description of 'algorithm' (although I don't know if the word has a technical definition, so that we may be left arguing about how we use the word personally). Otherwise, there could be no algorithm for listing all the natural numbers, for example.

stevetrewick 11y ago
IIRC the formal definition is something like (but probably not) : any finite set of steps that can be represented by a Turing (complete?) machine. I have seen definitions both with and without the requirement for a halting state. Fortunately someone will be along shortly to explain it properly.
- JadeNB 11y ago
  However, the existence of a halting state does not imply that all execution paths eventually reach it. Certainly I have never seen a definition (of an algorithm, rather than, say, a total language) that builds in that requirement; otherwise, what would be the objects considered in the halting problem? By this definition, they couldn't just be algorithms, or else "RETURN TRUE" would be a correct decision procedure.

mikeash 11y ago

That's an interesting point about randomness. You could implement a bogo-ish sort that's fully deterministic. Instead of randomly shuffling, iterate through all possible permutations of the input. Assuming the input contains no duplicates, there are n! permutations and one which is sorted, so your average running time will be n n!/2, which matches bogosort. Of course, in this age of cloud computing, we really should be using more modern terrible sorting techniques such as stacksort: https://gkoberger.github.io/stacksort/ https://gkoberger.github.io/stacksort/

cookingrobot 11y ago

That's technically called a "Las Vegas algorithm", because the answer is guaranteed correct, but the runtime has no guarantees. This is in contrast to "Monte Carlo algorithms" where the runtime is bounded, but the answer isn't necessarily correct.