Сортування підрахунком
Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
Приклад
Впорядкувати масив методом сортування підрахунком
n = int(input())
a =list(map(int,input().split()))
m=max(a)+1
mas1=[]
for i in range(m):
mas1.append(0)
for i in range(n):
j=a[i]
mas1[j]=mas1[j]+1
a.clear()
n1=len(mas1)
p=-1
for i in range(n1):
k=mas1[i]
p=p+1
while k>0:
a.append(p)
k=k-1
print(*a)