flat assembler
Message board for the users of flat assembler.

 Index > Heap > Sorting in O(1)! {Bead Sort}
Author
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

_________________
02 Nov 2010, 06:29
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17450
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

Joined: 21 Jul 2003
Posts: 2936
Location: vpcmipstrm
bitRAKE
That's okay because my abacus orbits a black hole.
(n is divided by some large constants.)
02 Nov 2010, 06:46
Tyler

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

Joined: 24 Aug 2004
Posts: 17450
revolution
What is ∞/∞?

Actually c < ∞
02 Nov 2010, 08:09
bitRAKE

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

_________________
02 Nov 2010, 12:48
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
@@:
```

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
```

Last edited by edfed on 02 Nov 2010, 13:51; edited 1 time in total
02 Nov 2010, 13:48
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17450
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.
02 Nov 2010, 13:50
edfed

Joined: 20 Feb 2006
Posts: 4240
Location: 2018
edfed
beads sort looks like bubble sort.
02 Nov 2010, 13:52
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.
02 Nov 2010, 21:02
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum