Counting Sort

Lab C Intermediate 20 points

Sort n marks between 0 and 100 with counting sort and print them.

Input

Line 1: n. Line 2: n integers.

Output

One line.

Example

Input

8
70 30 70 100 0 70 30 99

Output

0 30 30 70 70 70 99 100

Sample input available Sample output available

Editor

Hints

Global arrays start zeroed.

Count each value, then print each value count times.

Solution explanation

Counting sort is O(n + range) - faster than comparison sorts when the range is small.

Show solution

#include <stdio.h>

int count[101];

int main() {
    int n, x, printed = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        count[x]++;
    }
    for (int v = 0; v <= 100; v++) {
        for (int c = 0; c < count[v]; c++) {
            if (printed) printf(" ");
            printf("%d", v);
            printed = 1;
        }
    }
    printf("\n");
    return 0;
}

Output

Answer