forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathradix_sort.py
More file actions
49 lines (35 loc) · 1.16 KB
/
radix_sort.py
File metadata and controls
49 lines (35 loc) · 1.16 KB
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
"""
Radix Sort
Radix sort processes digits from least significant to most significant,
distributing elements into buckets for each digit and collecting them
back in order.
Reference: https://en.wikipedia.org/wiki/Radix_sort
Complexity:
Time: O(n * k) best / O(n * k) average / O(n * k) worst
Space: O(n + k) where k is the number of digits in the largest value
"""
from __future__ import annotations
def radix_sort(array: list[int]) -> list[int]:
"""Sort an array of non-negative integers using radix sort.
Args:
array: List of non-negative integers to sort.
Returns:
A sorted list.
Examples:
>>> radix_sort([170, 45, 75, 90, 802, 24, 2, 66])
[2, 24, 45, 66, 75, 90, 170, 802]
"""
position = 1
max_number = max(array)
while position <= max_number:
buckets: list[list[int]] = [[] for _ in range(10)]
for num in array:
digit = num // position % 10
buckets[digit].append(num)
index = 0
for bucket in buckets:
for num in bucket:
array[index] = num
index += 1
position *= 10
return array