자료구조 - 정렬 5 (Counting)

 

전체 정렬 개요의 설명은 여기를 참조
Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Radix 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조

 

Counting  Sort(계수 정렬)

 

간단하게 그림으로 이해할 수 있는 자료는 다음과 같다. 

 

계수 정렬 이해를 위한 그림

 

혹은 이를 간단하게 테스트해볼 수 있는 웹 페이지 링크도 있다. 여기를 들어가서 확인.

 

계수 정렬의 특징은 다음과 같다.

 

특성	설명
Not In-place 알고리즘	배열을 나누는 과정에서 나누어진 배열을 별도로 저장할 공간이 필요하다.
Unstable 알고리즘	같은 값의 데이터의 기존 순서 유지를 보장할 수 없다.

 

계수 정렬의 시간  / 공간 복잡도는 아래와 같다.

알고리즘	시간복잡도(최상)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
계수 정렬	O(n)	O(n+k)	O(n+k)	O(n)

 

우선, 기본적으로 Unstable 알고리즘으로 알려져 있지만 구현에 따라 Stable 정렬로 구현하는 것이 가능하다.

시간복잡도에서 n은 배열의 크기를 의미하며 k는 값의 크기를 의미한다. k는 예를 들어 숫자로 이루어진 배열이 10개 주어지는 데 그 숫자의 범위가 1 ~ 10억이라면 10억을 의미한다.

그러나 이 k값은 정렬 시 조정을 할 수 있고, 값이 작다면 영향이 낮아 경우에 따라 시간복잡도는 O(n)이라고도 볼 수 있다.

여기서 아래와 같은 의문이 발생할 수 있다.

1) 즉, 배열의 크기만이 아니라 값이 얼마나 큰지도 정렬 시간에 영향을 미친다. 왜 이런 현상이 발생할까?
2) 시간복잡도를 보면 n+k의 숫자가 크지 않다면 퀵 정렬의 성능(O(nlogn))보다 빠르다. 그런데 왜 보통 퀵 정렬을 대신 쓸까?

위의 이유를 이제부터 차근차근 알아보자.

 

 

정렬 과정

 

계수 정렬은 Counting 이라는 말에서 유추할 수 있듯이, 요소의 개수를 세어서 정렬하는 방식이다. 이는 다른 정렬 방식이 값을 비교하며 정렬하는 것과는 확연히 다른 차이점이다.

예를 들어, 아래와 같은 배열 arr이 있다고 생각해보자.

인덱스 i	0	1	2	3	4	5
배열 arr[i]	4	1	2	1	1	2

 

그러면, 계수 정렬은 위의 arr[i]의 값이 몇 번 등장했는지를 확인한다. 1이 3번, 2가 2번, 4가 1번 등장하였으니 이를 별도의 배열에 넣고 그 값을 이용해 정렬을 수행한다.

각 arr[i]의 값이 몇 번 등장했는지를 저장하는 배열 brr이 있다고 생각하면 다음과 같이 저장된다.

인덱스 i	0	1	2	3	4
배열 brr[i]	0	3	2	0	1

 

저장 시에는, arr[i]의 값에 해당하는 index에 1씩 더해서 저장하는 방식이다. 즉, 이와 같은 별도의 배열에 전체 숫자의 범위 중 각 숫자가 몇 번 등장했는지 저장해야 하기 때문에 값의 크기가 정렬에 영향을 미치는 것이다.

그래서 brr 배열 크기는 전체 값의 범위에 영향을 받는다. arr에 데이터가 10개 밖에 안되는데 데이터가 10 ~ 10억 까지 난잡하게 구성되어 있다면 계수 정렬이 정말 효율적이라고 볼 수 있을까?

 

그래서 계수 정렬은 모든 경우에 사용하기 어렵다. 아래를 참고

Point!

① 데이터의 범위가 데이터의 개수에 비해 너무 크지 않아야 성능을 제대로 낼 수 있다.
② 전체 범위의 숫자 빈도를 저장하는 별도 배열을 쓰기 때문에 범위가 크면 공간 낭비가 심할 수 있다.
③ Radix sort등 다른 정렬 방식의 Sub sort로 사용되는 경우가 더 많다.
④ 음수 또는 알파벳(char, string), 소수점(float) 배열에 대해서도 사용할 수 있다.(값을 조정해서 brr 배열에 저장하면 됨)
⑤ 하지만 string, float에 대해서 사용하는 것이 권장되지는 않는다.

 

위 Point 중 5번에 대해 좀 더 알아보자.

예를 들어, 소수점이 엄청 긴 데이터들이 즐비하였고 이를 정렬하고자 하는 경우를 예시로 들 때, 이 데이터 값들을 모두 소수점이 아닌 정수 값 등으로 변환해서 Counting 하는 것은 가능하다.

하지만, 이 때 전체 데이터 값의 크기가 너무 커지게 된다면 Counting Sort를 사용하는 의미가 퇴색된다. 차라리 O(nlogn)의 성능을 유지하더라도 다른 비교 방식의 정렬을 사용하는 것이 더 나을 수 있다.

혹여나, K라는 값이 데이터의 크기이고 K값이 아주 크지 않은 수준으로 유지된다고 하면 전체 O(kn)을 유지하여 거의 선형에 가까운 성능을 낼 수 있겠지만, 이러한 경우에 선형 수준 성능을 유지할 수 있는 방법은 Counting Sort 외에도 더러 있다.

Balanced Tree의 경우 거의 선형 성능 수준에 가깝게 진행이 가능하며, String이라면 Trie(트라이) 구조를 통해서도 가능하다. 심지어 Insertion Sort라도 분포 상태에 따라 O(n)의 성능에 가깝게 낼 수 있다.

따라서, Counting Sort 또한 정답이 될 수 없는 것은 아니지만, 데이터를 재구조화하는데에 따른 구현의 난이도도 있고 굳이 복잡한 데이터를 정렬하기에 항상 적합한 방식이라고 볼 수는 없다.

참조 : https://cs.stackexchange.com/questions/6641/counting-sort-on-non-integers-why-not-possible/6642

 

 

그럼 다음 과정은, 생성된 brr 배열을 modify 하는 과정이 필요하다. 어떻게 modify 되는지는 아래의 표를 참고하자.

인덱스 i	0	1	2	3	4	5
배열 arr[i]	4	1	2	1	1	2
배열 brr[i]	0	3	2	0	1	X (없음)
배열 brr[i]  Modify	0 (arr0 값)	3 (arr0 ~ arr1 합)	5 (arr0 ~ arr2 합)	5 (arr0 ~ arr3 합)	6 (arr0 ~ arr4 합)	X (없음)

 

brr 배열은 전체 범위인 4까지만 크기로 할당했기 때문에 index 5는 아예 생성되지 않았다. 배열 brr을 modify할 때는 누적합을 계산해서 저장해주면 된다.

왜 누적합을 해야 할까? 이 누적합의 결과가 기존 배열의 각 값이 어느 위치에 정렬되어야 하는지에 사용되기 때문이다.

 

위의 표는 이해를 돕기 위해 생성된 배열을 모두 표시한 것이며, 실제로는 아래와 같은 두 개의 배열이 생성된 상태일 것이다.

인덱스 i	0	1	2	3	4	5
배열 arr[i]	4	1	2	1	1	2
배열 brr[i]	0	3	5	5	6	X (없음)

 

이 상태에서 정렬을 하는 방법은 간단하다. arr 배열의 뒷 부분 부터 순회하며 위치를 계산해 결과 배열에 저장하면 된다. 아래를 보고 이해해보자. 정렬이 완료된 결과 배열은 result배열이다.

① arr[5] = 2, brr[2] = 5이다. 그러므로 result[5-1] = result[4] = 2 가 된다. brr[2]의 값을 1 뺀다. brr[2] = 4
② arr[4] = 1, brr[1] = 3이다. 그러므로 result[3-1] = result[2] = 1 이 된다. brr[1]의 값을 1 뺀다. brr[1] = 2
③ arr[3] = 1, brr[1] = 2이다. 그러므로 result[2-1] = result[1] = 1 이 된다. brr[1]의 값을 1 뺀다. brr[1] = 1
④ arr[2] = 2, brr[2] = 4이다. 그러므로 result[4-1] = result[3] = 2 가 된다. brr[2]의 값을 1 뺀다. brr[2] = 3
⑤ arr[1] = 1, brr[1] = 1이다. 그러므로 result[1-1] = result[0] = 1 이 된다. brr[1]의 값을 1 뺀다. brr[1] = 0
⑥ arr[0] = 4, brr[4] = 6이다. 그러므로 result[6-1] = result[5] = 4 가 된다. brr[4]의 값을 1 뺀다. brr[4] = 5

 

즉, arr배열의 값이 곧바로 brr배열의 index가 되며 그 brr배열의 값을 결과 배열의 index로 활용할 수 있는 것이다. 결과 배열의 index로 활용 시 1을 빼주는 이유는 0번 index부터 활용하기 위함이다.

또한 brr 배열의 값을 1 빼주는 이유는 해당 index를 이미 사용했기 때문이다. 결과는 아래와 같다.

인덱스 i	0	1	2	3	4	5
배열 result[i]	1	1	1	2	2	4

 

※ 잠깐, 왜 arr 배열의 뒤에서부터 순회할까? 그것은 Stable을 유지하기 위함이다. 앞에서부터 순회하면 Unstable 상태가 된다.

참고
이 계수 정렬은 문자열의 Suffix Array를 만들 때 효율적으로 사용된다.

 

 

코드로 구현

 

package com.test;

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args){

        // 전체 크기는 30으로 제한
        int[] arr = new int[30];
        for(int i=0; i < arr.length; i++){
            // Math.random을 통해 값의 범위는 0 ~ 19 까지로 제한
            arr[i] = (int)(Math.random()*20);
        }

        countingSort(arr);
        // 출력
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }

    public static void countingSort(int[] arr){
        // 최대값을 찾는다.
        int max = Arrays.stream(arr).max().getAsInt();

        // 음수가 전달될 경우를 대비, 최소값을 찾는다.
        int min = Arrays.stream(arr).min().getAsInt();

        // brr 배열(Count)의 크기를 결정
        int range = max - min + 1;

        // Count 배열이 바로 brr 배열이라고 보면 된다.
        int[] count = new int[range];

        // result 배열도 생성 ( 정렬이 완료된 배열이므로 기존 배열 크기와 동일하게 설정)
        int result[] = new int[arr.length];

        // 각 배열의 값이 몇 번 나왔는지 넣어주자.
        for(int i=0; i < arr.length; i++){
            count[arr[i] - min]++;  // 최소값을 빼줌으로써 0번 index부터 사용 가능
        }

        // count 배열의 누적합을 구함(Modify)
        for(int i=1; i < count.length; i++){
            count[i] += count[i-1];
        }

        // count 배열은 사실상 어디에 위치시킬지 값을 저장한 Modified 배열이므로 그 값을 통해서 result 배열에 원래 값을 저장
        for(int i = arr.length-1; i >= 0; i--){
            result[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        for(int i=0; i < arr.length; i++){
            arr[i] = result[i];
        }
    }
}

 

코드를 보면 크게 어렵지 않게 이해할 수 있습니다.

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.