자바 카운팅 정렬 Counting Sort 계수 정렬 완벽 이해하기

카운팅 정렬 Counting Sort 

카운팅 정렬은 시간 복잡도 O(n) 을 가지고 있기 때문에 많은 정렬 알고리즘 중에서 좋은 성능을 갖고 있다.

빠른 정렬 알고리즘에 속하는 퀵 정렬 (Quick Sort), 힙 정렬 (Heap Sort), 합병 정렬 (Merge Sort) 등의 평균 시간 복잡도가O(nlogn) 인 것을 보면 엄청난 속도를 가지고 있다는 것을 알 수 있다.

 

이처럼 빠른 속도를 가졌음에도 정렬이 필요한 상황에서는 퀵 정렬을 주로 사용한다.

그 이유에 대해서 알아보자.

 

정렬 과정

카운팅 정렬은 데이터 값이 몇 번 나왔는지 세주는 것이다. 정렬의 이름처럼 수를 counting 해주는 것.

 

다음과 같은 배열이 있다고 가정해보자.

 

 

1. 배열을 쭉 돌면서 해당 값을 index로 하는 새로운 배열의 값을 1 증가시킨다.

 

array[0] = 1 → counting[1] 값 1 증가

array[1] = 3 → counting[3] 값 1 증가

···

array[8] = 3 → counting[3] 값 1 증가

array[9] = 1 → counting[1] 값 1 증가

 

counting 배열은 1의 개수는 3개, 2의 개수는 1개, ··· 등 해당 인덱스 값의 개수를 담는 배열이다.

 

2. 완성된 counting 배열의 누적합을 계산한다.

 

counting[1] → counting[0] + counting[1]

counting[2] → counting[1] + counting[2]

···

counting[5] → counting[4] + counting[5]

 

누적합을 구하는 이유는 각 값의 시작점을 알기 위해서다.

아래에서 자세하게 살펴보자.

 

3. 최종적으로 정렬하기

 

counting 배열은 시작값을 알려주기 때문에 해당 값을 counting 배열의 값을 보고 넣어주면 된다. 

 

array[9] = 1, counting[1] = 3 으로 counting 배열의 값에서 1을 빼주고 새로운 result 배열에 넣어주면 된다.

result 배열에 넣어준 후에는 다음 값을 위해서 counting 배열의 값을 -1 해주어야 한다.

 

이 과정을 반복하면서 array 배열의 마지막 인덱스부터 진행하면 된다.

 

 

위 그림처럼 마지막 인덱스부터 순서대로 진행해주면 된다.

 

순서를 배치하는 과정에서 정렬의 기본인 두 개의 수를 비교하지 않기때문에 엄청나게 빠른 속도를 자랑하지만 몇 가지 단점이 존재한다.

 

누적합을 저장하기 위한 새로운 배열 counting 을 선언해주어야한다는 점인데 array 배열 값의 범위가 클수록 치명적이다. 예를 들어 array 배열에 1, 2, 3 그리고 1000000 의 값만 존재한다면 고작 4개의 값을 정렬하는데 counting 배열의 크기는 1000001로 메모리 낭비가 극심하다.

 

값의 범위에 따라서 메모리 낭비가 극심하기 때문에 빠른 속도를 자랑함에도 불구하고 주로 퀵 정렬을 사용하는 것이다.

 

구현

public class CountingSort {
    public static void main(String[] args) {
		
        int[] array = new int[100];		
        int[] counting = new int[11];	
        int[] result = new int[100];	
		
        // 랜덤 값 생성하기 (0 ~ 10)
        for(int i=0; i<array.length; i++) {
            array[i] = (int)(Math.random()*11);	
        }
 
        // 1번 과정
        for(int i=0; i<array.length; i++) {
            counting[array[i]]++;			
        }
		
        // 2번 과정
        for(int i=1; i<counting.length; i++) {
            counting[i] = counting[i] + counting[i-1];
        }
        
        // 3번 과정
        for(int i=array.length-1; i>=0; i--) {
            int value = array[i];
            
            counting[value]--;
            result[counting[value]] = value;
        }
    }
}