[Algorithm/Java] 카운팅 정렬 (Counting sort)

카운팅 정렬 (Counting sort)

카운팅 정렬은 정렬 시 데이터들의 개수를 세어 카운팅 배열에 저장하고 이후에 하나씩 꺼내오는 방식으로 정렬한다.

특정 조건이 부합할 때만 사용할 수 있지만, 데이터 수가 많더라도 중복된 값이 많이 분포되어 있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 

시간복잡도는 O(N + k)이다. k는 컬렉션(카운팅배열) 내부의 최대 숫자이다.

따라서 최대값이 너무 큰 경우에는 시간복잡도가 매우 커질 수 있다.

카운팅 정렬의 조건

1. 데이터가 양의 정수인 경우

카운팅 정렬은 기본적으로 0~최댓값의 인덱스를 가지는 배열에 데이터 등장 횟수를 카운팅 하는 방식이다.

따라서 양의 정수만 가능하다.

2. 데이터의 크기 범위가 제한 된 경우

위에서 언급했듯이, 최대값이 너무 큰 경우에는 시간복잡도가 커질 수 있다.

3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우

필수적인 조건은 아니지만, 데이터 크기 차이가 클수록 메모리 사용이 많아지게 된다.

---

핵심 이론

예제 배열

1. 가장 작은 데이터와 가장 큰 데이터가 모두 담길 수 있는 리스트를 생성한다.

위의 배열에서 가장 작은 값은 1, 가장 큰 값은 6이다.

따라서 1 ~ 6의 인덱스를 가진 카운팅 리스트를 만들어보자.

2. 배열을 순회하며 각 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

위와 같이 카운팅 리스트가 완성된다.

3. 완성된 카운팅 리스트에서 0인 값을 제외하고, 해당 인덱스의 데이터만큼 반복해서 출력한다.

---

Code

1. 카운팅 리스트 생성 (배열 이용)

public static List<Integer> countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();//최대값 찾기
    int[] cntArr = new int[max + 1]; //카운팅 리스트 생성

    //배열을 순회하며 각 데이터값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
    for (int i = 0; i < arr.length; i++) {
        cntArr[arr[i]]++;
    }
	
    List<Integer> result = new ArrayList<>(); //정렬된 데이터를 담을 list
    
    //완성된 카운팅 리스트에서 0인 값을 제외하고, 해당 인덱스의 데이터만큼 반복해서 출력한다.
    for (int i = 0; i < cntArr.length; i++) {
        if(cntArr[i] == 0){
            continue;
        }
        for (int j = 0; j < cntArr[i]; j++) {
            result.add(i);
        }
    }
    return result;
}

 

2. Map을 이용해서 등장하는 숫자의 개수 기록

public static List<Integer> countingSort2(int[] arr) {
	//key : 데이터 , value : 등장 횟수
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int x : arr){
        map.put(x, map.getOrDefault(x, 0) + 1);
    }
    //map의 keySet을 작은 순서대로 정렬한 리스트
    ArrayList<Integer> list = new ArrayList<>(map.keySet());
    Collections.sort(list);

    List<Integer> result = new ArrayList<>(); //정렬된 배열을 담을 리스트

    for (int i = 0; i < list.size(); i++) {
        int num = list.get(i);
        for (int j = 0; j < map.get(num); j++) {
            result.add(num);
        }
    }
    return result;
}