首页 > itarticle > age sort – uva 11462

age sort – uva 11462

admin 11月 12, 2020 0

Problem

Summary

Sort 2,000,000 integers between 1 and 100.

Analyse

First idea: fast sort, merge sort O(nlogn), TIMELIMIT!
Use the counting sort algorithm!
Complexity: O(n).

Code in C++

#include <cstring>
#include <cstdio>
using namespace std;
int n, age;
int first;
int a[100];
int () {
	while (scanf("%d", &n) && n) {
		memset(a, 0, sizeof(a));
		first = 1;
		for (int i = 0; i < n; i++){
			scanf("%d", &age);
			a[age]++;
		}
		for (int i = 1; i < 100; i++){
			for (int j = 1; j <= a[i]; j++)
				if (first) {
					printf("%d", i);
					first = 0;
				}
				else 
					printf(" %d", i);
		}
		printf("n"); 
	}
	return 0;
}