flat assembler
Message board for the users of flat assembler.
Index
> Heap > Sorting in O(1)! {Bead Sort} 
Author 

bitRAKE
It has been shown that you cannot sort a list of n elements using comparisons faster than O(nlgn). If the elements are confined to a small and finite range of values, then it is possible to sort in O(n) time.
I recently came across a very interesting sorting "algorithm". This algorithm can sort your elements in O(1) time!! Yes, thats true! But not on your traditional computers, which are modern versions of the VonNeumann machine. For this, you require an abacusyour first counting tool. On an abacus, you would represent each number by a set of beads. For example, the number 4 will be represented by 4 beads, and so on. Here is the algorithm: Arrange the list of numbers on the abacus in a way such that each row represents a number. THEN, allow the beads to fall freely. AND, you now have a sorted list of the original numbers. Consider an example. Let the original list of numbers be [3,7,1,5] On an abacus, the numbers would look like: Code: ooooo (5) o (1) ooooooo (7) ooo (3) Code: o (1) ooo (3) ooooo (5) ooooooo (7) source 

02 Nov 2010, 06:29 

revolution
It is not really O(1), it is O(n) since the distance & time to fall is proportional to n.


02 Nov 2010, 06:36 

bitRAKE
That's okay because my abacus orbits a black hole.
(n is divided by some large constants.) 

02 Nov 2010, 06:46 

Tyler
bitRAKE wrote: That's okay because my abacus orbits a black hole. 

02 Nov 2010, 07:44 

revolution


02 Nov 2010, 08:09 

bitRAKE
I found it...
∞/∞, had to compress it:


02 Nov 2010, 12:48 

revolution
edfed: You would need n1 parallel CPUs to do that sort in O(n) time. What you have shown is an (incomplete) bubble sort.


02 Nov 2010, 13:50 

edfed
beads sort looks like bubble sort.


02 Nov 2010, 13:52 

baldr
Without dedicated hardware (e.g. contentaddressable memory) its implementation seems to take O(n²) on average, as bubble sort does.


02 Nov 2010, 21:02 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on YouTube, Twitter.
Website powered by rwasa.