Transcript Bead-Sort

Bead-Sort
- A natural algorithm for sorting
Beads sort themselves out
Bead-Stack machine
The “tilt” operation
900
Bead-Sort: illustration 1
Sorting {3, 1, 2}
1. Drop 3 beads
(Remember, always from left-to-right)
2. Drop 1 bead
3. Drop 2 beads
1
2
3
Bead-Sort: illustration 2
Sorting {2, 3, 1}
1. Drop 2 beads
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 1 beads
1
2
3
Bead-Sort: illustration 3
Sorting {1, 3, 2}
1. Drop 1 bead
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 2 beads
1
2
3
Bead-Sort: illustration 4
Sorting {1, 3, 2, 4}
1. Drop 1 bead
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 2 beads
4. Drop 4 beads
1
2
3
4
Bead-Sort: illustration 5
Sorting {2, 4, 3, 2}
1. Drop 2 beads
(Remember, always from left-to-right)
2
2
2. Drop 4 beads
3. Drop 3 beads
3
4. Drop 2 beads
4
Level_Count
Simulating Bead-Sort with a program
• Two linear arrays used.
0
• Rod_Count keeps track of number
of beads in each rod.
0
1
• Level_Count records number of
beads in each level.
3
2
1
1
Rod_Count
• Finally, Level_Count will contain
sorted data.
Bead-Sort: Proof of correctness
Mathematical induction on number of rows of beads
Claims:
(i)
Rows of beads represent the same set of positive integers before and after
dropping down.
(ii) After dropping, each row has beads less than (or equal to) that on the row
directly below it.
1 row (k = 1)
2 rows (k = 2)
x
(i)
i
x
i
(iii)
x
(ii)
x+i
x
x+i
Bead-Sort: Proof of correctness
k+1th
row
k rows
the smallest amongst k rows
the smallest amongst k+1 rows
has already emerged on top
Parallel implementation of Bead-Sort
Using a digital circuit
flip-flops
cn 0
0 0 0
0 0 0 0
absence of bead - 0
1 1 1 0
presence of bead - 1
c2 1 1 0 0
c1 1 1 1 0
Data entry register
1
1
1
0
cn 0 0 0 0
0 0 0 0
1 1 0 0
c2 1 1 1 0
c1 1 1 1 0
Input from corresponding cell in
data entry register
cit
ci-1
Cit+1
Parallel implementation
1/2 A
1/3 A
1/6 A
Using an analog circuit
1 1 1 (no. 3)
1 0 0 (no. 1)
1 1 0 (no.2)
321
Calculating current
Resistor chain 1:
I1 = V1/R = 3/(1+2+3) = 1/2 A
Resistor chain 2:
I2 = V2/R = 2/(1+2+3) = 1/3 A
Resistor chain 3:
I3 = V3/R = 1/(1+2+3) = 1/6 A
‘Trim’ Voltage :
Trim( v ) =
1 if v >= 0.5
0 otherwise
sorted data
Trim
1
0.5 V
Trim
1
0.3 V
V2Trim 2
V1 2 
Trim
1
0.2 V
V3Trim 2
Trim
1V
0.7 V
0.3 V
3
3
3
Trim1 V
1.5 V
1
2
3
Trim0.5 V
1
1
2
v1 1 V
1
1
DATA ENTRY
0
0
1
Trim
0
(strings of 1’s similar to balls)
Increase voltage by 1 unit every time a ‘1’ is sent
v2
2V
v3
3V
Parallel simulation
Using a cellular automaton (CA)
initial
configuration
{2,1,3}
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
0
final
configuration
{1,2,3}
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
2
3
4
5
6
7
8
CA rules for Bead-Sort simulation
1
Bead-Stack machine
Loading the input (beads)
1
2
3
4
Pushing button-1 will make one bead
to drop down, pushing button-2 will
make two beads to drop down (in
parallel), and so on.
Bead-Stack machine
The “tilt” operation
900
Bead-Stack machine
Reading the output
Beads rolled down along rod-1 will have the label “1”, those rolled down along rod-2 will
have “2”, and so on.
1
1
1
1
labels stuck on the sides
(of the beads)
2
2
2
3
3
4
only label ‘3’ is seen
Bead-Stack machine
Complexity of inputting, sorting and outputting a list
Inputting a list: Using the gadget that loads a row-of-beads, we need N (loading)
operations to input a list of size N (into the frame of the Bead-Stack machine).
Sorting a list: We tilt the frame 90o (a single operation, from the Bead-Stack
machine’s perspective). The time taken by the falling beads to settle down is
sqrt(2h/g), where h is the height of the rods and g, the acceleration due to gravity. If we
fix the height of rods to be the same as the size (N) of the list, then the time taken is
given by sqrt(2N/g), i.e. O(sqrt(N)).
Outputting a list: Nothing needs to be done to explicitly output rows of beads; the
user could (literally) read the output (row by row).