| 2 | |
| 3 | |
| 4 | def countingSort(array): |
| 5 | size = len(array) |
| 6 | output = [0] * size |
| 7 | |
| 8 | # Initialize count array |
| 9 | count = [0] * 10 |
| 10 | |
| 11 | # Store the count of each elements in count array |
| 12 | for i in range(0, size): |
| 13 | count[array[i]] += 1 |
| 14 | |
| 15 | # Store the cummulative count |
| 16 | for i in range(1, 10): |
| 17 | count[i] += count[i - 1] |
| 18 | |
| 19 | # Find the index of each element of the original array in count array |
| 20 | # place the elements in output array |
| 21 | i = size - 1 |
| 22 | while i >= 0: |
| 23 | output[count[array[i]] - 1] = array[i] |
| 24 | count[array[i]] -= 1 |
| 25 | i -= 1 |
| 26 | |
| 27 | # Copy the sorted elements into original array |
| 28 | for i in range(0, size): |
| 29 | array[i] = output[i] |
| 30 | |
| 31 | |
| 32 | data = [4, 2, 2, 8, 3, 3, 1] |