Strangest Sorting Algorithms | Hacker News Reader

Strangest Sorting Algorithms

codoholicconfessions.wordpress.com

60 pointsbelter33 comments

Post list on an internet forum claiming you have sorted it (or maybe even better, that it's "unsortable"). Take list from angriest reply

That one could be implemented with sentiment analysis!

And now we succeeded using AI and manual intervention for yet another problem that could be implemented with a simple classical algorithm.

That’s actually Murphy’s law

Yes. Because this isn't the response you were hoping for. It could go wrong so it did.

For each number in the list, create an IT project with that many people on the team. The projects will finish in ascending sorted order.

That's just a more sophisticated version of sleep sort.

There is actually a better version of BogoSort that is deterministic.

The C++ implementation is very elegant:

    while(!std::next_permutation(v.begin(),v.end()));

The complexity is O(N!)

it's even better, isn't it? next_permutation returns false once it rolls over and returns the sorted version so you can drop the negation.

Strictly speaking that is the “correct” implementation of bogosort because it is deterministic (per my algorithms lecturer: for it to be an algorithm you must take the same steps each time for a given input. Obviously you could get around this by having the sort function take a seed and implement an RNG)

There are various definitions of "algorithm", but that one seems needlessly restrictive. Randomized algorithms are a thing, and there doesn't seem to be much reason to exclude them, to me.

I think the specific issue with the "randomly sort and see if its sorted" is that it is not guaranteed to ever complete.

Can't the same be said about the algorithm to generate the Collatz sequence for any given number? By that definition, I shouldn't be calling that an algorithm.

Is collatz the 2n+1&n/3 one?

Any way the algorithm to get the next number in a collatz sequence is deterministic and has best and worst case complexity of O(1).

You’re then just choosing to run that algorithm against its own output a (potentially) infinite amount of times.

That said I take you point. I realize in another reply that what I had totally failed to recognize was my lecturer not clearly explaining that the definition he used was that an algorithm must be executable on a Turing machine.

Yeah, Collatz operation is: if it's even divide by 2, otherwise multiply by 3 and add 1.

The gp post is asking: what if you make a procedure that runs that on a given input number, repeatedly, until you end up with the output 1, and give the sequence of numbers you visited on the way. Is that an algorithm?

Every number we've tried so far does go to 1, but it's unproven if they all do. It's possible that there exist cycles not containing 1, or maybe some inputs go to infinity. We haven't been able to prove either way.

> [...] the definition he used was that an algorithm must be executable on a Turing machine

Yeah, that's a pretty good reason to choose a certain definition of an algorithm (that otherwise might be awkward) when you have a model you're fitting it into.

It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm.

Aren't these the same steps for any given input?

  1) Roll dice to get random number N
  2) Get the Nth permutation of the input sequence (for some ordering of permutations)
  3) Permute input sequence
  4) If sorted: done, else goto step 1

You have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm.

Think of it as “can I run this algorithm on a Turing machine”

Sleep sort only works if the time to enumerate the list and schedule timers is sufficiently small relative to the multiplier.

I think a correct implementation would be sleep(x * k) where k is a constant factor determined by the platform

I have doubts that destroying the universe can happen in less than O(N).

I imagine it's constant time

That part is constant time. The O(N) is the random shuffle

You don't have to destroy the universe. Just kill yourself. You'll therefore only exist in universes where the list is sorted. Quantum suicide sort.

Algorithm #2 is also an algorithm that solves any problem as long as the solution is at all possible.

Want to pass an exam tomorrow? Set the machine to destroy the universe two days from now if you haven't passed the exam.

Internet poll sorting:

Create a poll asking to vote for the largest number, wait for results and put it at last. Repeat for remaining numbers. Oh wait that's selection sort. Nevermind.

>6 Stalin Sort

>8 Intelligent Design Sort

These don't sort the list.

Die, heathen traitor!

Sorted is in the eye of the beholder?

Stalin Sort definitely sorts the list correctly.

I hope I don't need to report you, comrade, for saying what is obviously a capitalist lie.

No algorithm sorts the list if it's already sorted.

That’s the wrong attitude if you’re using Stalin sort.

bang Next!

Your belief otherwise is either an evil capitalist lie or an insidious effort to undermine the principles on which your great nation is built. Either way you need to be shot unless you can start believing in the facts required for the greater good.

>These don't sort the list.

In this cases it is the list which sorts you. The end result is the same - the final observer perceives the list as sorted.

@dang I'm saddened to see this on HN. Should we really be platforming this kind of misinformation?

Reply on news.ycombinator.com