계수정렬 - Counting Sort

얼마 전 정렬 알고리즘의 기본적인 5가지를 알아보았다.

( 선택, 삽입, 버블, 합병, 퀵 )

 

하지만 빠르다는 합병이나 퀵의 시간 복잡도는 O(nlogN)으로 더 빠른 정렬이 있다는 사실을 알게되었고 , 그러한 알고리즘으로 Counting Sort에 대해 정리해보려한다. ( Counting Sort의 시간복잡도는 O(n))

 

소개

앞서 소개한 5개의 알고리즘 ( 하단 글 참고 )https://zepettoworld.tistory.com/71

정렬알고리즘

에서 O(n²)의 시간복잡도를 가지는 선택/삽입/버블은 옆의 수를 비교한다. 또한 nlog₂N 의 시간복잡도를 가지는 (퀵정렬은 최악의 경우가  n²) 합병/퀵 정렬은 2번씩 나누고 또 나눌때마다 정렬을 다시해야하므로 nlog₂N을 넘어설 수 가 없다. 따라서 O(n)의 시간복잡도를 가지기 위해서는 무언가를 비교하는 것이 아니라 다른 방식으로 우회하여 비교하는 방식이어야한다. 엥? 

 

원리

- 계수정렬은 각 원소들의 개수를 구하고 (1) 원소들을 오름차순대로 개수대로 나열하는 것이다. (2)

 

위에서 설명한대로 [4,6,2,3,3,1,5,3,5] 이라는 배열이 있다고 가정해보았을 때

1 : 1개

2 : 1개

3 : 3개

4 : 1개

5 : 2개

6 : 1개

1번의 과정대로 각 원소의 개수를 구하고 다음 원소들을 오름차순대로 개수대로 나열하겠다.

[ 1, 2, 3, 3, 3, 4, 5, 5, 6]

 

1번의 과정에서 각 배열의 개수대로 기록하기 위한 추가적인 저장공간을 생성하고 추가적인 저장공간의 인덱스에 counting을 해주는 방식으로 코드를 짜보면 될 것 같다. 

 

위 그림처럼 [4,6,2,3,3,1,5,3,5]를 가지는 numbers 배열의 값들을 개수대로 counts 배열 인덱스에 저장을 해둔다.

(ex. 0은 0개이므로 0, 1은 1개이므로 1번 인덱스에 1)

 

그리고 counts2 라는 배열에 다음과 같이 또 저장을 해준다.

counts라는 인덱스가 증가할때마다 전 인덱스의 값들을 더 해준다. 이러한 과정이 왜 필요할까.. count2의 인덱스를 하나씩 정리해보면 각 배열의 값은 (시작점 - 1) 이라는 점이다. 

 

예를 들어

numbers[0] = 4 -> counts2[4] = 6 -> 6-1=5 -> [ 0,1,2,5,5,8,9] -> [ x, x, x, x, x, 4, x, x, x ]  
numbers[1] = 6 -> counts2[6] = 9 -> 9-1 = 8 -> [ 0,1,2,5,5,8,8] -> [ x, x, x, x, x, 4, x, x, 6]

numbers[2] = 2 -> counts2[2] = 2 -> 2-1 = 1 -> [0,1,1,4,5,8,8] -> [ x, 2, x, x, x, 4, x, x, 6]

numbers[3] = 3 -> counts2[3] = 5 -> 5-1 = 4 -> [0,1,1,5,4,8,8] -> [x, 2, x, x, 3, 4, x, x, 6]

numbers[4] = 3 -> counts2[3] = 4 -> 4-1 = 3 -> [ 0,1,1,5,3,8,8] ->[x, 2, x, 3, 3, 4, x, x, 6]

numbers[5] = 1 -> counts2[1] = 1 -> 1-1 = 0  -> [0,0,1,5,3,8,8] -> [1, 2, x, 3, 3, 4, x, x, 6]

 

numbers[6] = 5 -> counts2[5] = 8 -> 8-1 = 7 [0,0,1,5,3,7,8] ->[1, 2, x, 3, 3, 4, x, 5, 6]

numbers[7] = 3 -> count2[3] = 5 -> 4-1 = 3 [0,0,1,5,2,7,8] -> [1, 2, 3, 3, 3, 4,x, 5, 6]

numbrts[8] = 5 -> count2[5] = 7 -> 7-1 = 6 [0,0,1,5,2,6,8] -> [1,2,3,3,3,4,5,5,6]

 

새롭게 저장공간을 취해야하므로 단점이 될 수 있다. 예를 들어 [4, 5, 2000, 1] 의 배열이 있을 경우 , 배열의 길이를 2000으로 잡아야하는 낭비가 발생할수 있다. 하지만 시간복잡도면에서 강력한 방법이 될 수 있다.

 

자바 구현