Counting sort handles small keys. Run it once per digit, and it can sort much larger numbers.
What to build
A least-significant-digit radix sort that shows the array after each pass.
Requirements
- Find the number of digits in the largest number.
- Do one stable counting pass for each digit, starting with the units.
- Print the whole array after each pass.
Input
The first line has n. The second line has the n numbers.
Output
One line per pass, with the numbers separated by spaces.
Constraints
1 ≤ n ≤ 200, and each number is from 0 to 99999.
Example
Input:
8
170 45 75 90 802 24 2 66
Output:
170 90 802 2 24 45 75 66
802 2 24 45 66 170 75 90
2 24 45 66 75 90 170 802
Why it works
Each pass is stable, so numbers with the same digit keep the order set by the earlier digits. After the last pass, the numbers are sorted by all their digits, in O(d × (n + 10)) time, with no comparisons between numbers.
Examples
8 170 45 75 90 802 24 2 66
170 90 802 2 24 45 75 66 802 2 24 45 66 170 75 90 2 24 45 66 75 90 170 802
1 7
7
Hints
Hint 1
Each pass must be stable, so go through the numbers in order and place them into a new array using counts.
Hint 2
Make the counts cumulative and fill the output from the last number to the first, or keep ten starting positions and fill from the first.
Hint 3
Use the largest number to decide how many digit passes are needed. The number 0 has one digit.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, a[200], out[200];
scanf("%d", &n);
int max = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if (a[i] > max) max = a[i];
}
int place = 1;
do {
int count[10] = {0};
for (int i = 0; i < n; i++) count[a[i] / place % 10]++;
for (int d = 1; d < 10; d++) count[d] += count[d - 1];
for (int i = n - 1; i >= 0; i--) out[--count[a[i] / place % 10]] = a[i];
for (int i = 0; i < n; i++) a[i] = out[i];
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
place *= 10;
} while (max / place > 0);
return 0;
}