bead sort Algorithm
The Bead Sort Algorithm, also known as Gravity Sort, is a natural sorting algorithm that works by visualizing the list of numbers as beads on an abacus. This algorithm is mainly used for sorting positive integers and is particularly efficient when dealing with numbers that have a small range of possible values. The key idea behind the algorithm is to represent each element of the list as a column of beads, where the height of the column corresponds to the value of the element. Then, the algorithm simulates the process of the beads falling due to gravity, causing them to stack up at the bottom, resulting in a sorted list of numbers.
To execute the Bead Sort Algorithm, first, the input list is transformed into a two-dimensional grid with rows representing the numbers in the input and columns representing their respective bead counts. Next, the algorithm iterates through the grid by moving the beads downwards, allowing them to "fall" and accumulate at the bottom row. This process is repeated for each column, effectively sorting the numbers in ascending order. Once all the beads have settled at the bottom, the algorithm transforms the grid back into a list, representing the sorted output. Although this algorithm is not widely used in practice due to its limitations in handling negative numbers and large datasets, it provides an interesting visualization of the sorting process and can be used as an educational tool to teach the basic concepts of sorting.
"""
Bead sort only works for sequences of nonegative integers.
https://en.wikipedia.org/wiki/Bead_sort
"""
def bead_sort(sequence: list) -> list:
"""
>>> bead_sort([6, 11, 12, 4, 1, 5])
[1, 4, 5, 6, 11, 12]
>>> bead_sort([9, 8, 7, 6, 5, 4 ,3, 2, 1])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> bead_sort([5, 0, 4, 3])
[0, 3, 4, 5]
>>> bead_sort([8, 2, 1])
[1, 2, 8]
>>> bead_sort([1, .9, 0.0, 0, -1, -.9])
Traceback (most recent call last):
...
TypeError: Sequence must be list of nonnegative integers
>>> bead_sort("Hello world")
Traceback (most recent call last):
...
TypeError: Sequence must be list of nonnegative integers
"""
if any(not isinstance(x, int) or x < 0 for x in sequence):
raise TypeError("Sequence must be list of nonnegative integers")
for _ in range(len(sequence)):
for i, (rod_upper, rod_lower) in enumerate(zip(sequence, sequence[1:])):
if rod_upper > rod_lower:
sequence[i] -= rod_upper - rod_lower
sequence[i + 1] += rod_upper - rod_lower
return sequence
if __name__ == "__main__":
assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]
