Bead sort: faster than O(N log N) sort

http://en.wikipedia.org/wiki/Bead_sort

by zkz • 17 years ago

27 19 17 years ago

en.wikipedia.org

jaydub• 17 years ago

http://en.wikipedia.org/wiki/Radix_sort

Yrlec4• 17 years ago

Radix-sort is actually not linear. The algorithm will only work if the word-length w>=log(n) (because otherwise you can't store all possible n) so O(nw) is practically the same thing as O(nlog(n))

tybris• 17 years ago

Not sure what you mean by storing all possible n. Radix sort is O(nw) and for most use-cases w is smaller than log(n).

pmjordan2• 17 years ago

That's certainly true in general, but by choosing a fixed-length word size (i.e. 16, 32 or 64 bit integers) you can preselect w so that runtime is predictably O(n). I can't see a way of doing that with most other O(n log(n)) sorting algorithms. Additionally, the constant factor is typically low compared to other algorithms.

amalcon• 17 years ago

There are "sorting algorithms" faster than O(n log n); that limitation only applies to comparison sorts. These typically have complexity depending on the keyspace (for example, counting-sort has linear complexity in whichever is greater, the size of the input list or the keyspace).

They're also typically kind of useless, as in this example, because we rarely care to sort an arbitrary list of integers with no metadata. Radix-sort is a rare exception, in that it can easily be modified to carry metadata, hence people actually using it in some applications.

Liron• 17 years ago

"They're also typically kind of useless, as in this example, because we rarely care to sort an arbitrary list of integers with no metadata."

O(n) sorting algorithms are only impractical if the size of the keyspace dwarfs the number of elements to be sorted. In general a key is a variable-length string of bits, which makes for an exponentially-sized keyspace, so you want to stick with comparisons of element pairs.

But "metadata" has nothing to do with it. The last bead in each BeadSort row can contain a sticker with some metadata. That kind of trick generalizes to all sorts.

praptak• 17 years ago

"The last bead in each BeadSort row can contain a sticker with some metadata."

Wrong. The beads in columns remain in the original order (not sorted) and so would these stickers.

bayareaguy• 17 years ago

Previously posted here http://news.ycombinator.com/item?id=257374

die_sekte• 17 years ago

Now we will need extra hardware just to do sorting!

ars• 17 years ago

Is there any theory on analyzing sorting real world objects? Like playing cards.

In a computer, picking the n'th item in an array is O(1), in the physical world it's O(n). In a computer inserting an item is O(n), but in the physical world it's O(1).

Are there any good algorithms for sorting playing cards?

iofthestorm• 17 years ago

I think Insertion sort tends to be the most natural sort for doing things like sorting playing cards. Anything else seems like it would be more of a hassle than it would be worth in real life.

karanbhangui• 17 years ago

I thought about this sort on my own a couple years ago, and I thought I'd discovered the most amazing thing in sorting :P

Not only did I realize I was beaten to the punch few years earlier, but also that efficiency is lost in implementation.

prodigal_erik• 17 years ago

If you have to represent each value in unary, how can you even set up the input and read the results in less than O(N^2), much less carry out the "fall"?

stcredzero• 17 years ago

http://en.wikipedia.org/wiki/Spaghetti_sort

The advantages of this sort:

1) It involves something ridiculous (in the CS context) like Pasta.

2) You have an excuse to play the theme from "The Good, The Bad, and The Ugly" in that section of the talk.

ralph• 17 years ago

The brightly coloured slides on CSP-style programming, using Occam, at http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/ include a O(n) "sort pump" starting on page 14 of http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/... that's also O(n) for space.

Those slides are an interesting read generally if you're not familiar with CSP/Alef/Limbo-style programming, despite the crufty Occam syntax.

Bead sort: faster than O(N log N) sort

Related Stories