| 1 | def countingSort(inputArray): |
| 2 | maxEl = max(inputArray) |
| 3 | |
| 4 | countArrayLength = maxEl+1 |
| 5 | countArray = [0] * countArrayLength |
| 6 | |
| 7 | for el in inputArray: |
| 8 | countArray[el] += 1 |
| 9 | |
| 10 | for i in range(1, countArrayLength): |
| 11 | countArray[i] += countArray[i-1] |
| 12 | |
| 13 | outputArray = [0] * len(inputArray) |
| 14 | i = len(inputArray) - 1 |
| 15 | while i >= 0: |
| 16 | currentEl = inputArray[i] |
| 17 | countArray[currentEl] -= 1 |
| 18 | newPosition = countArray[currentEl] |
| 19 | outputArray[newPosition] = currentEl |
| 20 | i -= 1 |
| 21 | |
| 22 | return outputArray |
| 23 | |
| 24 | inputArray = [2,2,0,6,1,9,9,7] |
| 25 | print("Input array = ", inputArray) |