Bead sort , also called gravity type , is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in the Bulletin of the European Association for Theoretical Computer Science. Both digital and analog bead hardware implementations can achieve the sorting time O ( n ); however, the implementation of this algorithm tends to be much slower in the software and can only be used to sort the list of positive integers. Also, it seems that even in the best case, the algorithm requires O ( n 2 ).
Video Bead sort
Ringkasan algoritme
Bead-like operations can be compared to the way in which the beads glide on parallel poles, as in the abacus. However, each pole may have a number of different beads. Initially, it might be useful to imagine the beads hanging on vertical poles. In Step 1, such a setting is displayed using a n = 5 sequence of beads on a vertical pole mx m = 4 . The numbers to the right of each row represent the number representing that row; rows 1 and 2 represent a positive integer 3 (since each contains three beads) while the top row represents a positive integer 2 (since it contains only two beads).
If we then let the beads fall, the rows now represent the same integer in sequential order. Line 1 contains the largest number set, while the line n contains the smallest. If the convention mentioned above line contains a series of beads at pole 1.. k and leave the pole k 1.. m blank has been followed , it will continue to happen here.
The act of allowing the beads to "fall" in our physical example has allowed a value greater than the higher row to propagate to the bottom row. If the value represented by the line a is smaller than the value contained in the line a 1 , some of the beads from the line a 1 will fall into in the line a ; this will inevitably happen, because the line a contains no beads in that position to stop the beads from the a 1 line from falling.
The mechanism underlying the bead type is similar to that behind some sort of calculation; the number of beads on each pole corresponds to the number of elements with values ​​equal to or greater than the polar index.
Maps Bead sort
Complexity
The type of beads can be implemented with four levels of common complexity, including:
- O (1): The beads all move simultaneously in the same time unit, as with the simplest physical examples above. It is an abstract complexity, and can not be implemented in practice.
- O ( ): In a realistic physical model using gravity, the time required to allow the beads to fall is proportional to the square root of the maximum height, proportional to n.
- O (n): The beads are moved one row at a time. These are cases used in analog and digital hardware solutions.
- O (S), where S is the sum of the whole number in the input set: Each bead is moved individually. This is the case when the bead sort is applied without the mechanism to help find the empty space under the beads, as in the software implementation.
Like the Pigeonhole type, a kind of unusual bead because in the worst case can do faster than O ( n log n ), the fastest performance might be for some sort of comparison in worst case. This is possible because the key to bead type is always a positive integer and a kind of bead exploits its structure.
Example
This example is written in Python. The strategy for "dropping" the beads may be slightly different, but it does the same job.
References and notes
External links
- "Bead-Sort: Natural Sort Algorithm" (PDF) . Ã, Ã, (114Ã, KiB)
- Bead Sort in MGS, bead type visualization applied in MGS programming language
- Bead Sort in MathWorld
Source of the article : Wikipedia
0 Comments