계수 정렬(Counting Sort)

🌟 비교 기반의 정렬 알고리즘
기본 성능 O(n^2) : 선택/버블/삽입/셸 정렬

향상된 평균 성능 O(nlogn) : 퀵/합병/힙 정렬 👉 비교 기반 정렬 알고리즘의 하한

 

🟩 이미 얻어진 데이터 분포 정보를 활용하는 정렬 알고리즘

계수/기수/버킷 정렬 👉 선형 시간 O(n) 가능

 

🟩 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘

기존의 정렬 알고리즘들은 위치를 바꾸며 정렬했지만, 계수 정렬은 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요 없음

 

🟩 특징 및 장단점

값 비교가 일어나지 않아 속도가 빠르다.

하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간 필요

👉 정렬해야할 수의 범위가 작을 때에만 유리하다.

 

EX) 0, 100, 2, 10, 10000 오름차순으로 정렬하기

예를 들어서 정렬해야 할 수가 0, 100, 2, 10, 10000이면 고작 5개의 수를 정렬하는데 0부터 10000까지의 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다.

 

(장) 데이터의 범위가 작을 때는 O(n)의 시간 복잡도를 가지므로 매우 빠르다.

(단) 데이터의 범위가 크면 만들어야 하는 배열의 크기가 크므로 메모리의 낭비가 심하다.

 

🟩 과정

1. 정렬하고자 하는 배열의 최댓값을 구하기

2. 최댓값 크기의 배열에 각 원소를 순회하며 해당 값이 몇 개인지 저장

3. 저장된 데이터를 순서대로 출력

 

EX) 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1, 2, 3, 5 ,2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1 정렬하기

 

0. 초기 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
0	0	0	0	0

 

1. 1번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	0	0	0

 

2. 2번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	1	0	0

 

3. 3번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	0	0

 

4. 4번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	1	0

 

5. 5번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	2	1	0

 

6. 6번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	2	2	1	0

 

바로 위와 같이 해당 크기의 원소를 만나는 경우 숫자를 1씩 더해가면 된다. 똑같은 방식을 반복하면 결과적으로 다음과 같이 된다.

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
8	6	8	4	4

 

이제 크기 1부터 5까지 해당 숫자만큼 출력하면 정렬은 끝난다. 즉, 1을 8번, 2를 6번, 3을 8번, 4를 4번, 그리고 5를 4번 출력하면 정렬이 이루어진다.

 

정렬 후 : 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 

 

static void countingSort() {
    // 정렬할 배열
    int[] array = {1, 3, 2, 4, 3, 2, 5, 3, 1 , 2,
            3, 4, 4, 3, 5, 1, 2, 3, 5 ,2,
            3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
            
    // 크기가 최대값 만큼임 계수 세기용 배열
    int[] count = new int[6];
    
    for (int i = 0; i < array.length - 1; i++) {
        count[array[i]]++;
    }
    
    // 계수만큼 i 출력. 0이면 출력하지 않는다
    for (int i = 1; i <= 5; i++) {
        if (count[i] != 0) {
            for (int j = 1; j <= count[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}

 

🟩 시간복잡도

배열에 있는 원소들의 개수만 세고 작은 수부터 나열하므로 O(n)

구체적으로는 O(n+k)라 할 수 있다. k는 배열의 최댓값