Counting sort

1. Problem

- 배열의 요소를 오름차순으로 정렬해보자.

- 정렬할 데이터의 범위를 알고 있다면 데이터의 개수를 세어서 정렬할 수 있다.

 

2. Input

1) int[] arr

 

3. Output

1) arr를 오름차순으로 정렬한 결과

 

4. Example

// 예시: 5 5 4 4 3 3 3 2 2 1
// 배열의 앞에서부터 읽어가며 카운팅을 한다.
// 5 -> count[5]++;
// 5 -> count[5]++;
// 4 -> count[4]++;
// ...
// 1 -> count[1]++;
// count = [0, 1, 2, 3, 2, 2]
// 이것을 바탕으로 정렬된 결과를 출력하면
// 1 2 2 3 3 3 4 4 5 5

 

5. Code

int[] arr = {1,2,3,4,5,5,4,3,2,1,2,4,3,1,2,4,5,3,2,1}; // 20개의 요소
int a = 1, b = 5; // 데이터의 범위는 [1, 5]이다.
int[] count = new int[b-a+2]; // 5-1+2=6개를 담을 배열을 만든다. 이때 0번째는 사용하지 않는다.

// 각 숫자가 몇 개 있는지 센다.
for(int i=0 ; i<arr.length ; i++)
    count[arr[i]]++;

// 개수를 바탕으로 정렬한 결과를 다시 arr에 저장한다.
int index = 0;
for(int i=a ; i<=b ; i++)
    if(count[i]!=0)
        for(int j=1 ; j<=count[i] ; j++)
            arr[index++] = i;

// 정렬 확인
for(int i : arr)
    System.out.print(i+","); // 1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,

- n개의 요소를 앞에서부터 읽어가며 정렬한다.

- 그러므로 시간 복잡도는 O(n)를 따른다.

- 배열의 모든 요소의 범위를 메모리에 표현할 수 있다면 계수 정렬이 압도적으로 빠른 성능을 보여준다.