Сортування підрахунком

Сортування підрахунком (англ. 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)

Завдання для самостійного виконання

1308: Сортування підрахунком

Page updated

Google Sites

Report abuse