Counting Sort

개요

Counting Sort는 정렬 알고리즘으로 O(n)의 시간 복잡도를 가진다.

정렬과정
a : 4,4,3,2,5,3,4,6,7,8,1 과 같은 수열을 정렬하면
b : 1,2,3,3,4,4,4,5,6,7,8 과 같이 오름차순 정렬을 가능하게 해주는 정렬이다.

그럼 Counting Sort가 어떻게 수열 A를 정렬해서 수열 B를 얻는지 알아보자

정렬과정

우선 각 숫자가 몇번 등장하는지 세어준다.

여기서 왜 이름이 Counting Sort인지 대략 감이 오기 시작한다.
각 숫자가 몇번 등장하는지 세어주기 때문이다.

참조 : https://bowbowbow.tistory.com/8, http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html