자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘

카운팅 정렬은 많은 알고리즘 중에 O(n)에 시간복잡도를 가지는 엄청난 성능을 가진 정렬 방식입니다.

보통 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort)이 빠르다는 정렬이지만 데이터끼리 직접 비교를 하기 때문에 O(NlogN)의 시간 복잡도를 가지는것이 한계입니다.

그렇다면 카운팅 정렬은 어떻게 속도의 한계를 극복할 수 있었을까요? 그리고 이렇게 빠른 속도임에도 불구하고 O(NlogN)의 시간 복잡도를 가지는 알고리즘을 사용하는 것일까요?

 

카운팅 정렬은 말 그대로 해당 숫자가 얼마나 출연했는지 카운팅 하면서 정렬하는 방식입니다.

1. 정렬 해야하는 원소의 범위만큼의 배열을 만든다.

2. 만든 배열 인덱스에 해당하는 수가 정렬해야 하는 배열에 있는 만큼 값을 넣는다.

3. 만든 배열의 앞의 숫자를 더하여 배열을 완성한다.

4. 해당 배열의 값의 -1을 한 위치에 새로운 배열의 값을 배치한다.

 

그림으로 설명하겠습니다.

---

---

---

---

 

이해가 되시나요? 그림으로 자세히 설명할려다 보니 글이 너무 많아졌네요.

그래도 글로만 보시는 것보다 수월하게 이해하실 수 있을 겁니다.

 

포인트는 해당 배열에 원소가 몇 번 등장하는지 카운팅 해서 배열을 재배치한다는 것입니다.

이로 인해 비교하지 않고 바로 정렬을 할 수 있어 속도가 굉장히 빠른 정렬 방식이 됩니다.

하지만 그에 비해 이해하셨듯이 메모리가 매우 낭비되는 정렬 방식입니다.

만약에 원소의 차이가 0~1억이라면 엄청난 메모리가 낭비되는 정렬입니다.

그래서 잘 사용하지는 않고 원소의 범위가 한정적인 정렬에서 사용합니다.

 

그럼 구현해 보도록 하겠습니다.

전체코드

public class Count_Sort {
    public static void main(String[] args) {
        int[] array = new int[10];
        int[] counting = new int[10];//배열의 원소의 범위 만큼 길이 설정
        int[] result = new int[array.length];

        //배열에 난수 저장
        for(int i=0; i<array.length; i++){
            array[i] = (int)(Math.random()*10);
        }

        //정렬전 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }

        //계수 정렬
        count_sort(array,counting,result);

        System.out.println();
        System.out.println();

        //정렬후 배열
        for(int i=0; i<result.length; i++){
            System.out.printf("%d ",result[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }
    }

    public static void count_sort(int[] array,int[] counting, int[] result){

        //카운팅 배열 입력
        for(int i=0; i<array.length; i++){
            counting[array[i]]++;
        }

        //카운팅 배열 누접합으로 변경
        for(int i=1; i<counting.length; i++){
            counting[i] += counting[i-1];
        }

        //뒷 배열부터 순서대로 카운팅 정렬의 -1의 인덱스에 해당 배열 입력
        for(int i = array.length-1; i>=0; i--){
            int value = array[i];
            counting[value]--;
            result[counting[value]] = value;
        }
    }

}

public static void count_sort(int[] array,int[] counting, int[] result){

    //카운팅 배열 입력
    for(int i=0; i<array.length; i++){
        counting[array[i]]++;
    }

    //카운팅 배열 누접합으로 변경
    for(int i=1; i<counting.length; i++){
        counting[i] += counting[i-1];
    }

    //뒷 배열부터 순서대로 카운팅 정렬의 -1의 인덱스에 해당 배열 입력
    for(int i = array.length-1; i>=0; i--){
        int value = array[i];
        counting[value]--;
        result[counting[value]] = value;
    }
}

해당 그림을 그대로 코드로 변경한 것입니다. 

구현 자체는 어려운 것이 없음으로 그림을 이해하셨다면 별문제 없이 구현을 잘하셨을 겁니다.

 

위에 구현을 이해하셨다면 좀 더 간단히 아래와 같이 정리할 수 있습니다.

import java.util.Scanner;

public class Number_10989 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[sc.nextInt()]++;
        }

        /*
        해당 배열을 그냥 처음부터 있는 수만큼 출력한다는 개념으로
        for문과 while문을 만들어 구현한다.
         */
        for (int i = 0; i < arr.length; i++) {

            while (arr[i]-- > 0) {
                System.out.println(i);
            }
        }
    }
}

간단한 구현이 되었는데 해당 원소를 카운트 하고 카운트한 배열을 처음부터 출력하되 카운팅된 만큼 출력을 하는 것입니다. 그러면 누적합을 하는 경우 없이 바로 정렬된 원소를 출력할 수 있습니다.