Sorting the Slow Way: Perversely Awful Randomized Sorting Algorithms (2007) [pdf] | Hacker News Reader

Sorting the Slow Way: Perversely Awful Randomized Sorting Algorithms (2007) [pdf]

hermann-gruber.com

35 pointsPascLeRasc14 comments

Open articleView on HN

I always liked the quantum bogo-sort algorithm:

1) Randomise list

2) if list not in correct order, destroy the universe

The universe that's left will have the correct answer.

Note that the random source should be truly (in quantum sense) random for this to work.

"Help, I used a PRNG and I accidentally destroyed all known universes"

Better check StackOverflow.

Choosing the swapped element from the head of the array while traversing backwards is even better:

https://gist.github.com/SpComb/b8c722abde2b04a94b14

And specific choices of random seed also have some impact :)

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.

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

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.

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.

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/

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.

Has anyone analyzed the MCMC version?

    while not sorted:
        swap(a[rand(n)], a[rand(n)])

I think it may helpful to decompose the permutation into circles, and create an equation system of time left from different states.

IIUC that's covered in the paper, as bozo-sort (or bozo-sort+ if the two random numbers are different).

Reply on news.ycombinator.com