| 1 | def countingSortForRadix(inputArray, placeValue): |
| 2 | # We can assume that the number of digits used to represent |
| 3 | # all numbers on the placeValue position is not grater than 10 |
| 4 | countArray = [0] * 10 |
| 5 | inputSize = len(inputArray) |
| 6 | |
| 7 | # placeElement is the value of the current place value |
| 8 | # of the current element, e.g. if the current element is |
| 9 | # 123, and the place value is 10, the placeElement is |
| 10 | # equal to 2 |
| 11 | for i in range(inputSize): |
| 12 | placeElement = (inputArray[i] // placeValue) % 10 |
| 13 | countArray[placeElement] += 1 |
| 14 | |
| 15 | for i in range(1, 10): |
| 16 | countArray[i] += countArray[i-1] |
| 17 | |
| 18 | # Reconstructing the output array |
| 19 | outputArray = [0] * inputSize |
| 20 | i = inputSize - 1 |
| 21 | while i >= 0: |
| 22 | currentEl = inputArray[i] |
| 23 | placeElement = (inputArray[i] // placeValue) % 10 |
| 24 | countArray[placeElement] -= 1 |
| 25 | newPosition = countArray[placeElement] |
| 26 | outputArray[newPosition] = currentEl |
| 27 | i -= 1 |
| 28 | |
| 29 | return outputArray |
| 30 | |
| 31 | def radixSort(inputArray): |
| 32 | # Step 1 -> Find the maximum element in the input array |