[Algorithm] 계수 정렬(Counting Sort)

✨계수 정렬(Counting Sort)

컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것,
즉 정수 정렬 알고리즘의 하나
키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 사용한다.

 

✨과정

1. 배열 생성
2. 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 인덱스를 인덱스 값만큼 출력

 

 

 

 

ex) 백준 수 정렬하기 3

https://www.acmicpc.net/problem/10989

import sys
n=int(sys.stdin.readline().rstrip())
li=[0]*10001
for i in range(n):
    a=int(sys.stdin.readline().rstrip())
    li[a]+=1


for i in range(1,len(li)):
    for j in range(li[i]): print(i)

입력숫자 범위(키):1~10,000

입력받는 수의 개수(항목):10,000,000

 

 

https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

 

 

 

 

 

 

🎈참고자료

https://computer-science-student.tistory.com/587

https://jeonyeohun.tistory.com/103