flat assembler
Message board for the users of flat assembler.

Index > Heap > Sorting in O(1)! {Bead Sort}

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2936
Location: vpcmipstrm
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 Von-Neumann machine. For this, you require an abacus--your 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)    
Now, allow all beads to freely fall vertically downwards..
Code:
o        (1)
ooo      (3)
ooooo    (5)
ooooooo  (7)    
.. and you get the sorted list!

source

_________________
¯\(°_o)/¯ unlicense.org
Post 02 Nov 2010, 06:29
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17450
Location: In your JS exploiting you and your system
revolution
It is not really O(1), it is O(n) since the distance & time to fall is proportional to n.
Post 02 Nov 2010, 06:36
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2936
Location: vpcmipstrm
bitRAKE
That's okay because my abacus orbits a black hole. Laughing
(n is divided by some large constants.)
Post 02 Nov 2010, 06:46
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
bitRAKE wrote:
That's okay because my abacus orbits a black hole. Laughing
(n is divided by some large constants.)
So it's O(0)? n/x -> 0, as x -> really big(infinity).
Post 02 Nov 2010, 07:44
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17450
Location: In your JS exploiting you and your system
revolution
What is ∞/∞?

Actually c < ∞
Post 02 Nov 2010, 08:09
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2936
Location: vpcmipstrm
bitRAKE
I found it...


∞/∞, had to compress it:


Description:
Download
Filename: r.zip
Filesize: 440 Bytes
Downloaded: 171 Time(s)


_________________
¯\(°_o)/¯ unlicense.org
Post 02 Nov 2010, 12:48
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4240
Location: 2018
edfed
it looks very interesting.

but in fact, how can it look like in X86?
if it is to sort only 32 bit values, it cannot be so complicated to do.

the beads representation can be virtualised by a real number.

Code:
mov eax,[esi]
cmp eax,[esi+4]
jl @f
xchg eax,[esi+4]
mov [esi],eax
@@:
add esi,4
    


but it would be very long to sort a real list....

or anything different can be interresting:
branchless
Code:
mov eax,[esi] ;get current item to sort
sub eax,[esi+4] ;sub from it the next item
sub [esi],eax 
add [esi+4],eax 
add esi,4
    


Last edited by edfed on 02 Nov 2010, 13:51; edited 1 time in total
Post 02 Nov 2010, 13:48
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17450
Location: In your JS exploiting you and your system
revolution
edfed: You would need n-1 parallel CPUs to do that sort in O(n) time. What you have shown is an (incomplete) bubble sort.
Post 02 Nov 2010, 13:50
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4240
Location: 2018
edfed
beads sort looks like bubble sort.
Post 02 Nov 2010, 13:52
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
Without dedicated hardware (e.g. content-addressable memory) its implementation seems to take O(n²) on average, as bubble sort does.
Post 02 Nov 2010, 21:02
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.