76 lines
1.3 KiB
C
76 lines
1.3 KiB
C
|
#include <stdio.h>
|
||
|
|
#define SIZE 42
|
||
|
|
|
||
|
|
int getDigit(int i, int pass) {
|
||
|
|
while (--pass && i) {
|
||
|
|
i = i / 10;
|
||
|
|
}
|
||
|
|
return i % 10;
|
||
|
|
}
|
||
|
|
|
||
|
|
void print(int *arr, int N) {
|
||
|
|
for (int i = 0; i < N; i++) {
|
||
|
|
printf("%d,", arr[i]);
|
||
|
|
}
|
||
|
|
printf("\n");
|
||
|
|
}
|
||
|
|
|
||
|
|
void radixSort(int *arr, int N, int pass) {
|
||
|
|
int bucket[10] = {0};
|
||
|
|
int output[N];
|
||
|
|
|
||
|
|
for (int i = 0; i < N; i++) {
|
||
|
|
bucket[getDigit(arr[i], pass)]++;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int i = 1; i < 10; i++) {
|
||
|
|
bucket[i] += bucket[i - 1];
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int i = N - 1; i >= 0; i--) {
|
||
|
|
output[bucket[getDigit(arr[i], pass)] - 1] = arr[i];
|
||
|
|
// this is important, to avoid collision
|
||
|
|
bucket[getDigit(arr[i], pass)]--;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int i = 0; i < N; i++) {
|
||
|
|
arr[i] = output[i];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int getDigits(int i) {
|
||
|
|
// this is used to offset the string
|
||
|
|
int count = 0;
|
||
|
|
do {
|
||
|
|
i /= 10;
|
||
|
|
count++;
|
||
|
|
} while (i);
|
||
|
|
|
||
|
|
return count;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
int arr[SIZE];
|
||
|
|
int N = 0;
|
||
|
|
char buf[SIZE];
|
||
|
|
fgets(buf, SIZE, stdin);
|
||
|
|
int offset = 0;
|
||
|
|
|
||
|
|
while (sscanf(buf + offset, "%d,", &arr[N]) != EOF) {
|
||
|
|
// remember the comma!
|
||
|
|
offset += getDigits(arr[N]) + 1;
|
||
|
|
N++;
|
||
|
|
}
|
||
|
|
|
||
|
|
int stepPass;
|
||
|
|
scanf("%d", &stepPass);
|
||
|
|
|
||
|
|
for (int i = 1; i <= stepPass; i++) {
|
||
|
|
radixSort(arr, N, i);
|
||
|
|
}
|
||
|
|
|
||
|
|
// only output the last step
|
||
|
|
print(arr, N);
|
||
|
|
return 0;
|
||
|
|
}
|