This Works only for Positive int's(+ve), but can be modified for Negative's also TC : O(n) SC : O(n)
(arr: list)
| 131 | |
| 132 | |
| 133 | def counting_sort(arr: list) -> list: |
| 134 | """This Works only for Positive int's(+ve), but can be modified for Negative's also |
| 135 | |
| 136 | TC : O(n) |
| 137 | SC : O(n)""" |
| 138 | n = len(arr) |
| 139 | maxx = max(arr) |
| 140 | counts = [0] * (maxx + 1) |
| 141 | for x in arr: |
| 142 | counts[x] += 1 |
| 143 | |
| 144 | i = 0 |
| 145 | for c in range(maxx + 1): |
| 146 | while counts[c] > 0: |
| 147 | arr[i] = c |
| 148 | i += 1 |
| 149 | counts[c] -= 1 |
| 150 | return arr |
| 151 | |
| 152 | |
| 153 | def main(): |