| 18 | // A function to do counting sort of arr[] according to |
| 19 | // the digit represented by exp. |
| 20 | static void countSort(int arr[], int n, int exp) |
| 21 | { |
| 22 | int output[] = new int[n]; // output array |
| 23 | int i; |
| 24 | int count[] = new int[10]; |
| 25 | Arrays.fill(count, 0); |
| 26 | |
| 27 | // Store count of occurrences in count[] |
| 28 | for (i = 0; i < n; i++) |
| 29 | count[(arr[i] / exp) % 10]++; |
| 30 | |
| 31 | // Change count[i] so that count[i] now contains |
| 32 | // actual position of this digit in output[] |
| 33 | for (i = 1; i < 10; i++) |
| 34 | count[i] += count[i - 1]; |
| 35 | |
| 36 | // Build the output array |
| 37 | for (i = n - 1; i >= 0; i--) { |
| 38 | output[count[(arr[i] / exp) % 10] - 1] = arr[i]; |
| 39 | count[(arr[i] / exp) % 10]--; |
| 40 | } |
| 41 | |
| 42 | // Copy the output array to arr[], so that arr[] now |
| 43 | // contains sorted numbers according to current |
| 44 | // digit |
| 45 | for (i = 0; i < n; i++) |
| 46 | arr[i] = output[i]; |
| 47 | } |
| 48 | |
| 49 | // The main function to that sorts arr[] of |
| 50 | // size n using Radix Sort |