[알고리즘] - 카운팅 정렬(Counting Sort / 계수 정렬)

카운팅 정렬은 말 그대로 정렬을 위한 알고리즘입니다. 수 많은 알고리즘 중에도 시간 복잡도가 O(n) 으로 효율이 좋습니다.

보통 정렬 알고리즘 중에서 빠른 건, 흔히 알고 있는 퀵정렬, 힙정렬, 합병정렬 등이 있다는 걸 알고 계실겁니다.

이들의 평균 복잡도는 O(nlogn) 인 것에 비하면 카운팅 정렬이 성능이 좋다는 걸 알 수 있습니다.

 

사실 정렬은 데이터끼리 직접 비교하는 경우가 많습니다. 그렇기 때문에 데이터를 직접 비교한 정렬 알고리즘일 경우, O(nlogn) 을 갖는 시간 복잡도 보다 작아지는 건 어렵습니다.

 

카운팅 정렬은 어떻게 이를 극복한 것이고, 그럼에도 불구하고 퀵 정렬 같은 알고리즘을 더 많이 사용하는 이유는 무엇일까요?

 

아래 블로그에 카운팅 정렬하는 방법에 대해서 잘 설명이 되어 있으니, 카운팅 정렬을 모르실 경우 보셔도 좋습니다.

 

[참고]

https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

 

즉, Counting Sort 가 수열의 길이보다 수의 범위가 극단적으로 클 경우 메모리 낭비가 될 수 있습니다.

수열의 길이 < 수의 범위 (극단적으로 차이가 날 경우) X

각기 상황에 맞게 정렬 알고리즘을 써야하는 상황에서 시간복잡도가 더 좋은 카운팅 정렬을 사용하기 보단 퀵이랑 병합 정렬을 더 선호하게 되는 이유가 이러합니다.

 

 

구현

// 카운팅 정렬
public class Algoritmn {
    public static void main(String[] args) {
        int[] arr = new int[101];  // [수 범위]
        
        // 카운팅 배열 세팅
        for (int i = 0; i < 50; i++) {  // [수열의 길이]
            int temp = (int) (Math.random() * 101);
            System.out.print(temp + " "); // 정렬 해야할 숫자.
            arr[temp]++; // counting 배열
        }

        System.out.println("\n"); // 개행
        
        
        for (int i : arr) {
            System.out.print(i + " ");
        }

        System.out.println("\n"); // 개행

        // 정렬
        for (int i = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                System.out.print(i + " ");
            }
        }
    }
}

 

카운팅 정렬 - 백준 알고리즘 문제 추천

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

[추가로 CountingSort 구현 방법 시각적으로 볼 수 있는 링크]

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort