Решение задачи №41 «Сортировка подсчетом» с ACMP

Условие задачи

На планете «Аурон» атмосфера практически отсутствует, поэтому она известна своими перепадами температур в различных точках. Известно, что эти перепады колеблются от -100 до 100 градусов. Нашим специалистам удалось выяснить значения температур в N точках этой планеты. К сожалению, эти значения вычислены с большими погрешностями, поэтому их решили округлить до целых чисел. Хотелось бы наглядно видеть участки с повышенной и пониженной температурой. Вам требуется помочь. Вы должны упорядочить температуры участков по неубыванию.

Входные данные
В первой строке входного файла INPUT.TXT задано натуральное число N - количество участков (N ≤ 106). Во второй строке через пробел записаны целые значения температур этих участков, не превосходящие 100 по абсолютной величине.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести разделенные пробелом значения температур всех известных участков, которые должны следовать друг за другом в порядке неубывания.

Решение на C++


    #include<stdio.h> 

void CountSort(int a[], int n)

{ 

	int b[201]={0},i,j,k; 

	for(i=0;i<n;i++)b[a[i]+100]++;

	i=0; 

	for(j=0;j<201;j++) 

	while(b[j]){a[i]=j-100;i++;b[j]--;} 

} 

main()

{ 

	int a[1000000],i,n; 

	scanf("%d",&n); 

	for(i=0;i<n;i++)scanf("%d",&a[i]); 

	CountSort(a,n); 

	for(i=0;i<n;i++)printf("%d ",a[i]); 

}

Условия задач взяты с сайта acmp.ru