Sort n exam marks into increasing order with counting sort. Every mark is a whole number from 0 to 100.
What to build
A counting sort for exam marks.
Requirements
- Count how many times each mark from 0 to 100 appears.
- Write out each mark as many times as it was counted, in increasing order.
- Do not compare two marks with each other.
Input
The first line has n (1 ≤ n ≤ 1000). The second line has the n marks.
Output
The marks in increasing order, separated by spaces.
Constraints
1 ≤ n ≤ 1000, and every mark is from 0 to 100.
Example
Input:
8
3 1 4 1 5 2 3 0
Output:
0 1 1 2 3 3 4 5
Why it works
The value of a mark is also its index in the counting array, so no comparisons are needed and the time is O(n + 101).
Examples
Example 1 · Input
8 3 1 4 1 5 2 3 0
Expected output
0 1 1 2 3 3 4 5
Example 2 · Input
3 100 0 50
Expected output
0 50 100
Hints
Hint 1
Make int count[101] = {0} and add 1 to count[mark] for every mark.
Hint 2
Then for each mark from 0 to 100, print it count[mark] times.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
int count[101] = {0};
for (int i = 0; i < n; i++) {
int mark;
scanf("%d", &mark);
count[mark]++;
}
int printed = 0;
for (int mark = 0; mark <= 100; mark++) {
for (int c = 0; c < count[mark]; c++) {
if (printed++ > 0) printf(" ");
printf("%d", mark);
}
}
printf("\n");
return 0;
}