>>> data = [-1, 2, -5, 0] >>> bucket_sort(data) == sorted(data) True >>> data = [9, 8, 7, 6, -12] >>> bucket_sort(data) == sorted(data) True >>> data = [.4, 1.2, .1, .2, -.9] >>> bucket_sort(data) == sorted(data) True >>> bucket_sort([]) == sorted([]) Tru
(my_list: list, bucket_count: int = 10)
| 32 | |
| 33 | |
| 34 | def bucket_sort(my_list: list, bucket_count: int = 10) -> list: |
| 35 | """ |
| 36 | >>> data = [-1, 2, -5, 0] |
| 37 | >>> bucket_sort(data) == sorted(data) |
| 38 | True |
| 39 | >>> data = [9, 8, 7, 6, -12] |
| 40 | >>> bucket_sort(data) == sorted(data) |
| 41 | True |
| 42 | >>> data = [.4, 1.2, .1, .2, -.9] |
| 43 | >>> bucket_sort(data) == sorted(data) |
| 44 | True |
| 45 | >>> bucket_sort([]) == sorted([]) |
| 46 | True |
| 47 | >>> data = [-1e10, 1e10] |
| 48 | >>> bucket_sort(data) == sorted(data) |
| 49 | True |
| 50 | >>> import random |
| 51 | >>> collection = random.sample(range(-50, 50), 50) |
| 52 | >>> bucket_sort(collection) == sorted(collection) |
| 53 | True |
| 54 | >>> data = [1, 2, 2, 1, 1, 3] |
| 55 | >>> bucket_sort(data) == sorted(data) |
| 56 | True |
| 57 | >>> data = [5, 5, 5, 5, 5] |
| 58 | >>> bucket_sort(data) == sorted(data) |
| 59 | True |
| 60 | >>> data = [1000, -1000, 500, -500, 0] |
| 61 | >>> bucket_sort(data) == sorted(data) |
| 62 | True |
| 63 | >>> data = [5.5, 2.2, -1.1, 3.3, 0.0] |
| 64 | >>> bucket_sort(data) == sorted(data) |
| 65 | True |
| 66 | >>> bucket_sort([1]) == [1] |
| 67 | True |
| 68 | >>> data = [-1.1, -1.5, -3.4, 2.5, 3.6, -3.3] |
| 69 | >>> bucket_sort(data) == sorted(data) |
| 70 | True |
| 71 | >>> data = [9, 2, 7, 1, 5] |
| 72 | >>> bucket_sort(data) == sorted(data) |
| 73 | True |
| 74 | """ |
| 75 | |
| 76 | if len(my_list) == 0 or bucket_count <= 0: |
| 77 | return [] |
| 78 | |
| 79 | min_value, max_value = min(my_list), max(my_list) |
| 80 | if min_value == max_value: |
| 81 | return my_list |
| 82 | |
| 83 | bucket_size = (max_value - min_value) / bucket_count |
| 84 | buckets: list[list] = [[] for _ in range(bucket_count)] |
| 85 | |
| 86 | for val in my_list: |
| 87 | index = min(int((val - min_value) / bucket_size), bucket_count - 1) |
| 88 | buckets[index].append(val) |
| 89 | |
| 90 | return [val for bucket in buckets for val in sorted(bucket)] |
| 91 |