[알고리즘] 카운팅 정렬(Counting Sort)

카운팅 정렬

리스트를 한번 스캔하면서 각 항목이 리스트에 몇 번 나타났는 지 빈도수를 계산

빈도수가 구해지면 가장 작은 항목부터 순서대로 빈도수만큼 나열

 

입력리스트 [14, 11, 12, 12, 15, 12]

입력의 제한과 추가 공간의 크기

기수 정렬과 같이 이 방법에서도 정렬을 위해 항목의 킷값들을

서로 비교하지 않았다.

각 항목의 빈도수를 세었을 뿐

 

대신 각 항목의 빈도수를 저장할 메모리를 추가 사용

킷값은 0~9

입력리스트[1, 4, 1, 2, 7, 5, 2]