Hacker News Reader

Hacker News

Comment by shultays | Hacker News Reader

Parent Full thread

shultays

Imo does not approach the simplicity of sleep sort: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

Also I am pretty sure I saw this algorithm before. Doesn't it have a name?

View on HN

If this doesn't have a name (I didn't see one in the paper), I propose “interview sort”.

All sorts are interview sorts - that's the only context in which they come up, for most programmers.

That's probably true, however didn't the default sort change between python2 and python3, as a newer, faster algorithm was found and implemented?

Bogosort is pretty simple, too.

  while not is_sorted(a) do
    shuffle(a)

However the shuffle function hides a surprising amount of complexity. It is nontrivial to write a correct shuffle function. [1]

But Bogosort isn't even the worst sorting algorithm out there! There is also Worstsort [2].

[1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[2]: https://arxiv.org/abs/1406.1077

Shuffling is even less tricky if you're not trying to do it in place, if you're not trying to do it in linear(ithmic) time, or if you're not trying to induce a uniform distribution over all permutations (but rather just want some positive probability for all of them). Relaxing any combination of these conditions works just fine for Bogosort.

It would even suffice to just swap two random elements every iteration!

My gut says that combining that with other sort cycles in some magic ratio could do magical things. I'm quite wrong quite often ofc but the adventure is out there!

Fun fact: Fisher-Yates samples a uniform distribution over permutations and is therefor capable of producing any permutation, so you can sort any array in linear time using Fisher-Yates with its RNG replaced by a appropriate oracle. (So the complexity of sorting a array mostly reduces to the complexity of determining which permutation it's in relative to a sorted version.)

I think most C++ implementation of bogosort use std::next_permutation

You can turn a sort into a shuffle by replacing the comparator with a random coin flip, and you already have defined a sort algorithm, so there's no added code complexity.

    fn bogosort(a, comparator):
      while not is_sorted(a, comparator) do
        bogosort(a, rand)

You can't turn all sorts (not even all comparison sorts!) into a shuffle by replacing the comparator with a random coin flip. In fact your code post is a demonstration of that fact.

a good (even) shuffle is not easy.

Sleep sort is heap sort. The heap is just built into your OS.

Sleep sort is meant as a joke. Obviously, everybody understands there exists no O(1) GP sorting algorithm.

Assuming GP means General Purpose, yes, everyone who took an intro to algorithms should know that no sorting algorithm that relies on comparisons can do better than O(n*log(n)).

But non-comparison algorithms [0] like radix sort [1] that rely on simplifying assumptions are not a joke and can be used in practice in many real-world cases.

[0] https://en.wikipedia.org/wiki/Sorting_algorithm#Non-comparis...

[1] https://en.wikipedia.org/wiki/Radix_sort

No general purpose sorting algorithm period can do better than O(n * log(n)), regardless of comparison or otherwise. For a radix sort with a complexity of O(n * w) where w is the key length, w converges to log(n) in the general case since the number of bits needed to represent n values grows logarithmically with n, hence you arrive back to O(n * log(n)). The O(n * log(n)) is an information theoretic result that applies even to radix sort, to be more precise the optimal sorting algorithm is Θ(n!).

If you fix w to a constant, then certainly one can claim that radix sort is O(n), but then so are comparison sorts as well.

That's not to say that radix sort isn't useful in practice, just because two sorting algorithms have the same asymptotic bounds doesn't mean they are equal, but it is to say that its performance is a matter of evaluating the constants rather than how it scales.

> since the number of bits needed to represent n values grows logarithmically with n

What you say only applies to sorting n unique/distinct keys. With no prohibition on duplicate keys, n & w vary quite independently. In this more general setting, radix sorting is indeed "really" O(nw) and w could be like 8 bits for some giant data set (EDIT and order is absolutely a useful property even with dups since there can be satellite data with the keys - also possibly bounded!). This is a common talking past each other problem in this area. To your credit you made this assumption explicit. (EDIT: "General purpose" may have some semantic unclarity, I suppose.)

In terms of relevance, everyone has their own, but my personal experience is that most (but not all) real world data allow both duplicate keys and bounding key width. In particular, the largest n data sets have been the least likely to have a prohibition on duplicate keys, and also the most likely to have small w (with a few exceptions). The random access pattern of memory writes in the passes of a radix sort may (or may not) be a problem, and constant factors matter, of course (as you also say). So tying w to n was has always seems a very special and somewhat artificial case to me.

I also have never heard of any practical O(n) comparison sort for fixed w before. Can you perhaps give a reference to some such algorithm? Thanks!

At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values surely you’re going to run into a similar log n factor that the gp threw at the radix sort?

It depends how you count. There can be O(n log(n)^2) as you say, but I believe there are some comparison based algos where you only have to compare "fewer bits" to decide each comparison. So bit-wise cmps might still be O(n log n). However, you do have to move whole w-bit keys which is w bits wide. So, in full cost (cmp + space moves) unless you can do tricks to avoid the whole move, the comparison sorts do scale worse than radix-like digital sorts. And on general purpose CPUs people certainly compare batches of 8/16/32/64 bits at a time in HW. Personally, I think radix really does scale better, but maybe @Kranar can clarify his claim. (EDIT: there is often a random write pattern to digital sorts that can slow them down at massive scales, but that is definitely an {important} constant factor/different kind of "real machine" analysis.)

Maybe it has more to do with the actual distribution/form of the data? From my understanding radix sort can be incredibly fast when the numbers have fixed digits and evenly distributed in a predefined range (like phone numbers) but will be ineffective for floating point numbers or uneven distributions with extreme outliers.

That is why I specified "General Purpose". The moment you know something more about the data there might exist an opportunity to exploit that information to improve the algorithm.

Which is an interesting topic in itself. Many times I have met people who said with absolute authority "no, it is not possible to implement this" only to be confronted with a counterexample. And that is because real life is rarely about spherical cows in vacuum.

I have once implemented a transactional, log-based database for credit card terminal (20MHz ARM, 2MB total unified memory).

The read (get value for key) operation was O(n^3) which the reviewers decided is "ABSOLUTELY FUCKING UNACCEPTABLE" (their words).

The fun started when I asked them to suggest better implementation. They could not come up with anything even remotely as fast.

And the basic reason was that n was guaranteed to be small as there wasn't even much space on the device for any more data. Other than that it exploited fantastic read ahead capability of the device plus it was so simple (basically couple nested loops) that CPU cache could be used very effectively.

I remember their O(nlog(n)) was never faster and actually about 50 times slower in most operations.

I'm consistently amazed at how willing people are to make assumptions about optimizations with problems that don't fit their assumptions.

Nice job.

I think main reason is our flawed education. The tasks you are being given at school are usually constructed so that they fit the idealized knowledge you just learned.

What it teaches people is to short cut the critical path of reasoning which is to first make sure you actually understand the problem and then the problem actually fits the assumptions. People are not taught that even a small divergence from assumptions can have dramatic difference on the actual solution or applicability of what they think is a solution. They are also not taught the actual assumptions or spot how they look. They talk about CS algorithms as if they worked on idealized computers, but then run them on real ones.

At school this is not taught because when it seems the problem fits the material it almost always is. People are actually rewarded for jumping to conclusions as this helps them go through material faster.

If you don't learn anything about the world you bring your learning with you and try to apply it to real world and that's how a lot of developers operate.

Especially in tech, you can usually look up solution to any problem easily. But for some reason this is the part everybody emphasizes rather than recognize knowing when to apply the solution is way more valuable.

I also think it is part of the wisdom behind "premature optimization is root of all evil".

What is wrong with Leetcode and similar, in a nutshell.

I once watched someone implement a heap in PHP in order to sort 4 domain names in order of priority and be able to resort them. The idea was I guess that at some point there may be 5 or even 6 of these and then we would really need the heap…

Amazing story, thanks for sharing!

Actually, for any specific size of N, every algorithm is O(1)...

I can’t believe someone implemented that in jq: https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#j...

Pretty interesting implementation not actually sleeping tho.

https://en.wikipedia.org/wiki/Insertion_sort ?

Reply on news.ycombinator.com