계수 정렬(Counting Sort)

계수 정렬(Counting Sort)

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

위와 같은 25개의 숫자가 있다고 가정해봅시다. 여기서
"5이하인 자연수들을 오름차순으로 정렬하세요"
라는 '범위 조건' 있는 경우에 한해서는 매우 빠른 알고리즘이 바로 계수 정렬 입니다. 계수 정렬의 속도는 O(N) 으로 다른 퀵 정렬, 힙 정렬, 병합 정렬보다도 빠른 속도입니다.

계수 정렬은 Counting Sort 의 말그대로 "크기를 기준으로 각각의 크기별로 카운팅해준다" 입니다.
크기별로 카운팅할 수 있는 이유는 범위 조건 이 존재하기 때문에 이렇게 분류를 할 수 있는 것입니다.

크기별로 카운팅을 해주었다면 해당 크기마다 작은 순서대로 쭉 적어놓으면 됩니다.

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

1이 총 6번, 2가 총 8번, 3이 총 3번, 4가 총 5번, 5가 총 3번이 출력됩니다. 그리고 순서대로 출력하면

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

이렇게 출력이 완료됩니다.

---

계수 정렬의 코드입니다.

public class Main {
    public static void main(String[] args) {
        int[] count = new int[5];
        int[] arr = {
                1, 2, 3, 2, 4, 1, 2, 3, 4, 5,
                4, 5, 2, 5, 2, 3, 4, 1, 2, 4,
                1, 2, 2, 1, 1
        };
        Count.countingSort(arr, count);
    }
}

class Count {
    public static void countingSort(int[] arr, int[] count) {
        for (int i = 0; i < count.length; i++) {
            count[i] = 0; // 각 크기별로 0으로 초기화
        }
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - 1]++; // -1을 해주는 이유 : 인덱스는 0부터 시작
        }
        for (int i = 0; i < count.length; i++) {
            if (count[i] != 0) {
                for (int j = 0; j < count[i]; j++) {
                    System.out.printf("%d ", i + 1);
                }
            }
        }
    }
}

 

지금까지 정렬 알고리즘의 참고 자료는 나동빈님 유튜브를 통해 정리하였습니다. 중간중간 구글이나 다른 유튜브 자료를 참고하여 정리하였습니다.