[알고리즘] 정렬 - 카운팅 정렬(counting sort, 계수 정렬)

🟡 카운팅 정렬(counting sort, 계수 정렬)

- 다른 정렬 알고리즘들과는 다르게 입력 배열의 값을 비교하지 않고, 각 값의 등장 횟수를 세어 정렬하는 방식

- 따라서 입력 배열의 값의 범위가 제한되어야 한다.

- 카운팅 정렬은 입력 배열의 크기가 N, 입력 값의 범위를 K라고 할 때, O(N+K)의 시간 복잡도를 가진다.

- 입력 값의 범위가 큰 경우에는 메모리 사용량이 많아진다.

 

 

🟡 카운팅 정렬 진행 과정

카운팅 정렬의 기본 아이디어는 각 입력 요소의 등장횟수를 기록하기 위해 카운트 배열을 사용하는 것

① 입력 배열을 순회하며 각 요소의 등장 횟수를 카운트 배열에 기록한다. 카운트 배열의 인덱스는 입력 요소의 값이고, 각 인덱스의 값은 해당 요소의 등장 횟수다.

② 카운트 배열을 누적 합 배열로 변환한다. 누적 합 배열은 정렬된 배열에서 각 요소의 마지막 위치를 가리킨다.

③ 입력 배열을 역순으로 순회하며, 각 요소를 정렬된 위치에 배치하고 누적 합 배열을 업데이트 한다.

→ 입력배열[i] 값의 누적합에 해당하는 위치에 값을 대입한다. 입력배열[i] 값이 하나 없어졌으므로 해당 값에 대한 누적합을 1 감소시킨다.

④ 정렬된 결과를 새로운 배열에 저장한다.

 

 

🟡 카운팅 정렬은 양수만 가능할까?

일반적으로 양수 정렬에 대해 사용되지만, 음수를 포함하는 배열에도 사용할 수 있다.

다만 음수 정수를 처리하기 위해서는 추가적인 단계가 필요하다.

입력 배열에서 최솟값을 찾고, 모든 요소에 최솟값의 절댓값을 더한다.

그 후 모든 정렬이 완료된 후 다시 원래의 음수 형태로 복원한다.

 

 

🟡 카운팅 정렬 예시 코드(Java)

import java.util.Arrays;

public class CountingSort {
    public static int[] countingSort(int[] arr) {
        // 입력 배열에서 최댓값을 찾아서 범위를 결정합니다
        int max = Arrays.stream(arr).max().getAsInt();

        // 카운트 배열을 생성하고 모든 요소를 0으로 초기화합니다
        int[] count = new int[max + 1];

        // 입력 배열의 각 요소의 등장 횟수를 카운트 배열에 기록합니다
        for (int num : arr) {
            count[num]++;
        }

        // 카운트 배열을 누적 합 배열로 변환합니다
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 정렬된 결과를 저장할 배열을 생성합니다
        int[] sortedArr = new int[arr.length];

        // 입력 배열을 역순으로 순회하며 정렬된 위치에 배치합니다
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int index = count[num] - 1;
            sortedArr[index] = num;
            count[num]--;
        }

        return sortedArr;
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 3, 4, 3};
        int[] sortedArr = countingSort(arr);

        System.out.println("입력 배열: " + Arrays.toString(arr));
        System.out.println("정렬된 배열: " + Arrays.toString(sortedArr));
    }
}

- 실행 결과

입력 배열: [4, 1, 3, 4, 3]
정렬된 배열: [1, 3, 3, 4, 4]

 

 

🟡 카운팅 정렬 예제

이전에 백준 10989번 문제를 풀면서 카운팅 정렬을 사용한 적이 있다.

해당 문제 링크 ↓

https://seohyun0916.tistory.com/244

[Baekjoon] 10989 - 수 정렬하기 3

문제를 보면 N이 10^7로 매우 크기때문에, O(N^2)과 같은 알고리즘을 쓰면 풀 수 없었다.

또한 입력 범위가 10000보다 작거나 같은 자연수라고 제한이 되어있기 때문에 카운팅 정렬을 쓸 수 있었다.

 

이 문제 같은 경우는 정렬된 결과를 출력하면 됐기때문에, 위에서 설명한 과정보다 훨씬 쉽게 풀이했었다.

단순 카운트 배열을 순회하면서 각 인덱스의 값 만큼 수를 출력하는 방식