FilesExpand file tree

main

/

bead_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (41 loc) · 1.5 KB

main

/

bead_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (41 loc) · 1.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

"""

Bead Sort

Bead sort (also known as gravity sort) simulates how beads settle under

gravity on an abacus. It only works with non-negative integers.

Reference: https://en.wikipedia.org/wiki/Bead_sort

Complexity:

Time: O(n) best / O(n * max_value) average / O(n * max_value) worst

Space: O(n * max_value)

"""

from __future__ import annotations

def bead_sort(array: list[int]) -> list[int]:

"""Sort an array of non-negative integers using bead sort.

Args:

array: List of non-negative integers to sort.

Returns:

A sorted list.

Raises:

ValueError: If any element is negative.

Examples:

>>> bead_sort([6, 3, 4, 1, 5, 2])

[1, 2, 3, 4, 5, 6]

"""

if any(num < 0 for num in array):

raise ValueError("Bead sort only works with non-negative integers.")

max_value = max(array) if array else 0

grid = [[0] * len(array) for _ in range(max_value)]

# Drop beads (place beads in columns)

for col, num in enumerate(array):

for row in range(num):

grid[row][col] = 1

# Let the beads "fall" (count beads in each row)

for row in grid:

bead_count = sum(row)

for col in range(len(array)):

row[col] = 1 if col < bead_count else 0

# Read sorted values from the grid (rightmost column has fewest beads)

n = len(array)

sorted_array = [0] * n

for col in range(n):

sorted_array[col] = sum(grid[row][n - 1 - col] for row in range(max_value))

return sorted_array