Talk:Bead sort

Sorry, but it's not quite accurate to say that this algorithm is order (N). It's equivalent to the well-known "bin sort" aka Pigeonhole_sort, and it's only order(N) if the number of items to be sorted exceeds the range of possible values. Otherwise it's Omega(range of possible values), and for many real-world problems the range is a very large number compared to the size of the list.

Recall that to represent the integer 7 in a beadsort, you need an abacus that's at least seven beads tall. That means that after turning it sideways, you need to scan at least 7 spots (bins) to see if any beads fell there. If you want to allow positive and negative integers from +/- 64,000, you need to scan 128,001 bins. It's an O(128,001) algorithm - not efficient if you have only 1,000 items to sort. In general, beadsort is (theoretically) more efficient than a traditional algorithm like quicksort only where N log N > range of possible values. Just using 32-bit integers as keys, you're talking about a range of over 4.2 billion, so you're looking at a list size on the order of 2^27 (about 128 million entries) before beadsort can achieve the claimed efficiency.

Actually, I've overstated my case. You could establish a mapping (eg, a hash function) into some smaller range, and as long as the mapping was rapid & easily reversible and collisions were infrequent, you'd stay close to the claimed efficiency. But the usefulness of the algorithm is still limited either to domains where suitable low-collision mappings can be found quickly or, as I've said before, to domains where the list to be sorted is large compared to the range of values.

It's quite an interesting paper - the concept of natural algorithms is promising, and I'm not aware of any previous parallel implementations of binsort. If input and readout can be implemented efficiently then this will be quite an exciting development, and very useful for the range of problems indicated. But as currently written, the article's claims are overblown.

I also think O(n) is wrong. This is only achievable if the hardware is able to scale with the problem size; that is, if your abacus grows to match the size of the input. Otherwise, the asymptotic complexity notation is meaningless. --Doradus 18:49, 9 May 2006 (UTC)

It's also untrue that software implementations can't match the complexity of the hardware ones. Parallel software implementations can, as long as the number of processors scales with the range. (And this range-dependent hardware cost also exists for hardware implementations.) --Xplat 19:24, 13 August 2006 (UTC)

If it on average sorts in O(S) time where S is the sum of all elements of the array, if the array were a bunch of zeroes and ones wouldn’t it sort in less than O(n) time? 73.169.206.87 (talk) 17:04, 20 April 2021 (UTC)

Clarity of mathematics and consistency

I have attempted to make the formulae in this article consistent in form with one another by converting them all to LaTeX, but, as you can probably see, the formula for $O({\sqrt {n}})$ is inconsistently large compared to the other formulae. For some reason (probably improper syntax resulting from my own lack of LaTeX skill) the commands "\small", "\scriptsize" etc. do not seem to work here. If anybody can further improve the consistency in the LaTeX, that would greatly improve the article.

One more thing is that this article is currently written with highly techincal language. I doubt that a lay-person would understand most of it. For that reason, I am about to add a "too technical" tag to the article (since I am not ready to undertake simplifying the writing myself just yet).

--InformationalAnarchist 6 July 2005 18:41 (UTC)

Physical model

The physical model is claimed to have O(n) time complexity, but that's wrong. In a relativistic universe it's O(n). Even in a Newtonian universe, you'd have to place it over a large gravitating plate (O(range of values) radius) to get O(sqrt n) time, and you couldn't do better than that with gravity unless you increase the thickness of the gravitating plate with n. (In that case you can make it scale just about arbitrarily, but a time-only complexity analysis hardly seems appropriate.) In any case, the Newtonian model is not realistic and with relativity it's O(n) regardless of the source of impetus as long as the geometry is even very roughly as illustrated.

You also have to pay O(n*range) cost for material for the poles.

--Xplat 19:19, 13 August 2006 (UTC)

so is this used anywhere other than abacuses?

Considering it "requires special hardware", it would help the reader to know if any such implementations exist and are used in any significant way. --Apantomimehorse 21:40, 20 August 2006 (UTC)

It's a natural algorithm it's not well suited to emulation. look for applications that involve ordering physical objects (eg: index cards)

coputationally pigeonhole sore is atleast as efficient and eaiser to implement. 118.90.20.246 (talk) 17:51, 20 December 2011 (UTC)

possible? implementation

C++ and possibly lisp code here: http://rosettacode.org/wiki/User_talk:MichaelChrisco —Preceding unsigned comment added by 67.182.50.44 (talk) 05:36, 23 August 2010 (UTC)

Zero

This algorithm also works with zeros, doesn't it? An abstract empty row remains still empty after sorting, being above all the beads. --Nikayama NDos (talk) 06:04, 16 August 2015 (UTC)

Unsourced assertion that is impossible.

"Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n^2) space."

An algorithm cannot use more space than time. — Preceding unsigned comment added by Sugarfrosted (talk • contribs) 03:20, 27 March 2019 (UTC)

On the example implementation

The old example was sloppy in terms of both naming and code style, made only tolerably better by edits from other contributors. I've updated the page with a version (disclaimer: of my own) that matches the beadsort process more succinctly.

Regarding efficiency: the transposed_list = [n - 1 for n in transposed_list] line creates a new list on every iteration, while alternatives like transposed_list[:] = (n - 1 for n in transposed_list) or for i in range(len(transposed_list)): transposed_list[i] -= 1 or for index, value in enumerate(transposed_list): transposed_list[index] = value - 1 avoid this — should one of them be used instead, or is it better to keep the less-efficient version for any clarity it affords? (I mean, the whole code snippet should probably be viewed as an unoptimized example anyway)

Also, if the comments are insufficient, I beg anyone who can improve them to please do so :) Wriight (talk) 02:18, 1 May 2019 (UTC)