계수 정렬 (Counting Sort)

계수 정렬이란?

각 원소들 간의 비교 없이, 크기를 기준으로 개수를 세어 정렬하는 알고리즘

 

 

시간 복잡도

O(N)

 

 

진행 과정

1. 각 크기에 해당하는 데이터의 개수를 count배열에서 세어준다.

2. count배열의 누적합을 구한다.

3. 누적합을 기준으로 해당 index에 data를 넣는다.

 

데이터가 담긴 A배열, 개수를 세어줄 C배열

 

각 크기의 개수

 

누적합 구하기

 

A배열의 마지막 인덱스부터 C배열의 값을 참조하며 B배열에 정렬

 

 

 

 

코드

public class CountingSort {
    public static void main(String[] args) {
        int[] a = {2, 5, 3, 0, 2, 3, 0, 3};
        a = sort(a);
        System.out.println(Arrays.toString(a));
    }

    public static int[] sort(int[] a) {
        int max = Collections.max(Arrays.asList(a)); // 최대값 찾기
        int[] b = new int[a.length];
        int[] c = new int[max + 1]; // 최대값의 크기만큼 배열 크기 지정
        Arrays.fill(c, 0);
        // 각 원소 갯수 계산
        for (int i = 0; i < a.length; i ++) {
            c[a[i]] += 1;
        }
        // 누적합 계산
        for (int i = 1; i < c.length; i ++) {
            c[i] += c[i - 1];
        }
        // 누적합을 이용해 정렬
        for (int i = a.length - 1; i >= 0; i --) {
            b[-- c[a[i]]] = a[i];
        }
        return b;
    }
}

 

 

계수 정렬의 장단점

장점

- 일정 조건에서 속도가 매우 빠르다.

- 안정(stable) 정렬이다.

- 구현이 단순하다.

 

단점

- 최대값의 크기 만큼 메모리가 필요하다. (공간 복잡도=O(k), k는 최대값)

- 최대값의 크기에 따라 시간 복잡도가 O(k)가 될 수 있다.

  ex)

    C배열 초기화 과정 : O(k)

    C배열 counting 과정 : O(n)

    C배열 누적 과정 : O(k)

    B배열 초기화 과정 : O(n)