Sorting integers and the corresponding algorithms is one of the first basic topics one learns in computer science. Bubble-Sort, Insertion-Sort, Merge-Sort, Quick-Sort, Radix-Sort and even many more are discussed during the first classes. For a general purpose sorting algorithm, that is one that is based on comparison operations, it is known that one can not do better than $\mathcal{O}(n\log n)$.
Radix-Sort for example, which is not a general purpose algorithm, since it works only for integers, has a running time for $k$-digit integers of $\mathcal{O}(kn)$.
The sorting algorithm which i want to discuss today is Bead-Sort. It is based on a funny little idea to let gravity make the work for you. It has a theoretical runtime (assuming gravity is for free) of $\mathcal{O}(1)$. Implementing this on a normal pc would actually destroy this runtime because the gravity has to be programmed somehow.
However, it works as follows: Assume we have a list of integers $3,6,3,1,4$. Little beads, that are lined up on a stick vertically, are forming these integers horizontally. An abacus would, for example, be a perfect tool for this kind of sorting.
\begin{array}{l | c c c c c c}
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Let the gravity begin.
\begin{array}{l | c c c c c c}
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
\hline\\
\end{array}
The beads fall until they are all stacked up on the last row. The sorted list of integers can then be extracted row by row.
| Lemma. Assuming that gravity is an $\mathcal{O}(1)$ operation, and neglecting input and output operations, Bead-Sort sorts a given list in $\mathcal{O}(1)$. |
Informal proof. You can view Bead-Sort as Simultaneous Bubble-Sort. Bubble-Sort takes an integer, say the one at the bottom, and moves the integer via comparison upwards (like it bubbles towards the surface) until it reaches a larger number. There it stops. It does so for every integer one after another. Here, it is similar, but all this bubbling happens more or less concurrently and from the top to the bottom.
To see this, look what happens if we drop the rows one after another instead of concurrently:
\begin{array}{l | c c c c c c}
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&|&|&|&|&|&|\\
3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&|&|&|&|&|&|\\
1&\huge\bullet&|&|&|&|&|\\
&|&|&|&|&|&|\\
4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
The bottom line can not drop any further, so we let the second to last row drop onto the last row.
\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
&6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&&|&|&|&|&|&|\\
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1&\huge\bullet&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Nothing happens. Now, we let the let third to the last row drop. First, it drops onto the second to the last row.
\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
&6&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet\\
&&|&|&|&|&|&|\\
\rightarrow&3-2=1&\color{red}{\huge\bullet}&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1+2=3&\huge\bullet&\color{red}{\huge\bullet}&\color{red}{\huge\bullet}&|&|&|\\
&&|&|&|&|&|&|\\
&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
Since, the dropping row has two beads more, these additional beads drop onto the row below, indicated by the red-colored beads. This "operation" is equal to a swap operation, i.e., the two rows exchange their length.
Hence, whenever a larger row drops onto a smaller row, they exchange their length, i.e., the number of beads in that rows. Consequently, a larger row drops down and swaps its length, until it reaches a larger row.
The next step would be to let the second row (now colored orange) drop onto the new third row:
\begin{array}{c l | c c c c c c}
&3&\huge\bullet&\huge\bullet&\huge\bullet&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&6-5=1&\color{orange}{\huge\bullet}&|&|&|&|&|\\
&&|&|&|&|&|&|\\
\rightarrow&1+5=6&\color{red}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}&\color{orange}{\huge\bullet}\\
&&|&|&|&|&|&|\\
&3&\huge\bullet&\color{red}{\huge\bullet}&\color{red}{\huge\bullet}&|&|&|\\
&&|&|&|&|&|&|\\
&4&\huge\bullet&\huge\bullet&\huge\bullet&\huge\bullet&|&|\\
\hline\\
\end{array}
They exchange their length and the large row will drop in the same manner until it reaches it final position.
Executing this simultaneously is Bead-Sort and hence yields a sorted list of integers.
Q.e.d.
# Practical Implications #
Has Bead-Sort any practical implications? There exists an implementation on special purpose hardware, which allows a runtime of around $\mathcal{O}(n)$. With standard mechanism it is hard to believe that it can be implemented in such a way, that is becomes more efficient than that.
Note one has not to use gravity, but also any other mechanism that pulls the beads at one column downwards. For example some electric or magnetic forces could be used to manipulate a given certain arranged input list.
\begin{array}{c || c | c | c | c | c | c |}
\hline
\rightarrow&\bullet&\bullet&...&\bullet & & \\
\hline
\rightarrow&\bullet&\bullet&...& & & \\
\hline
...&...&...&...& & & \\
\hline
\rightarrow&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
\rightarrow&\bullet&\bullet&...&\bullet&\bullet&\\
\hline
\end{array}
Apply some kind of pulling force to each column that makes each "bead" move downwards.
\begin{array}{c | c | c | c | c | c | c |}
\hline
&\bullet&\bullet&...&\bullet & & \\
\hline
&\bullet&\bullet&...& & & \\
\hline
&...&...&...& & & \\
\hline
&\bullet&\bullet&...&\bullet&\bullet&\\
\hline
&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
&\color{red}{\downarrow}&\color{red}{\downarrow}& \color{red}{\downarrow}&\color{red}{\downarrow}&\color{red}{\downarrow}&\color{red}{\downarrow}
\end{array}
Readout the sorted integer list from each row.
\begin{array}{c | c | c | c | c | c | c |}
\hline
\leftarrow&\bullet&\bullet&...&\bullet & & \\
\hline
\leftarrow&\bullet&\bullet&...& & & \\
\hline
...&...&...&...& & & \\
\hline
\leftarrow&\bullet&\bullet&...&\bullet&\bullet&\\
\hline
\leftarrow&\bullet&\bullet&...&\bullet&\bullet&\bullet\\
\hline
\end{array}
Is it possible and does this yield a non-negligible advantage?
No comments:
Post a Comment