카운팅 정렬(Counting sort)

카운팅 정렬

• 원소간 비교없이 정렬할 수 있는 정렬이다.
• 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방식.
• 시간 복잡도는 O(n+k)로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다.
• 정렬을 위한 길이n의 배열 하나, 계수를 위한 길이 k의 배열 하나가 필요하다.

 

동작방식

그림1

 

그림2

그림2에서 보면 a의 배열에서 가장 큰 값이 3이기 때문에  

배열 c를 0~3까지 잡아준다.

그림3

0 -> 1개

1 -> 3개

2 -> 0개

3 -> 2개

처럼 배열a에 들어있는 숫자의 갯수를 카운팅해준다.

그리고 c를 누적합 형태로 바꿔준다. 여기서 누적합의 의미를 알아보자

0이라는 숫자는 0번째 인덱스에 위치하고

1이라는 숫자는 1~3번째 인덱스에 위치하고

2라는 숫자는 4~3 즉 없고

3이라는 숫자는 4~5번재 인덱스에 위치한다는 뜻이다.

 

그렇다면 이를 이용해 정렬하는 모습을 살펴보자

a배열의 맨뒤에서부터 시작한다.

현재 c배열의 1인덱스는 4라는 숫자를 가지고 있다.

c배열의 1인덱스 자리를 -1해주고 그 위치로 보내준다.

 

마찬가지로 3의 인덱스는 6이다 -1을 해주고 그 자리에 넣는다

 

위의 방식처럼 하면  정렬이 완료된다.

 

 

카운팅정렬은 안정정렬의 형태를 가질 수 있다.

누적합을 기반으로 aux배열에 원소를 넣을 때 기존 배열a의 가장 오른쪽 인덱스에서 시작하면 된다.

 

만약, 첫번째 인덱스부터 시작한다면 어떻게 될까????

 

a배열에 0번째 인덱스에 1은 aux배열의 3번배열에 들어가게 되어 안정정렬이 되지 못한다.

 

 

 

 

 

이곳에서 시각적으로 카운팅정렬을 해볼 수 있다.

www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

 

 

카운팅 정렬의 장점

• 정렬하려는 수의 범위가 작고 숫자의 갯수가 많다면 좋은 효율을 보여준다
• 안정정렬이다.

 

카운팅 정렬의 단점

• 만약 수의 범위가 크다면 메모리의 낭비가 심하다
• ex) a[]={1,100,1000} 이라면 카운팅 정렬을 하기위해 배열의 길이를 1000개 잡아야 한다.

 

 

참고

bowbowbow.tistory.com/8

soobarkbar.tistory.com/101

yaboong.github.io/algorithms/2018/03/20/counting-sort/