[Java+Python]카운팅 정렬(Counting Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]퀵 정렬(Quick Sort)

 

카운팅 정렬은 말 그대로 세어서 정렬하는 방식이다.

 

그래서 무엇을 세느냐 하면, 아래에서 보겠지만 정렬 대상이 대는 원소의 등장 횟수를 전부 센다.

 

이후 원소의 최댓값에 따라 누적합을 보유한 배열을 만든 뒤, 그 배열의 원소를 근거로 대상 배열을 정렬하는 식이다.

 

카운팅 정렬의 시간 복잡도는 O(N + k)로, 여기서 k는 타깃이 되는 배열 원소의 최댓값을 의미한다(개수가 아니다).

 

즉, 가장 큰 데이터의 값에 따라 효율이 정해지며, 범위가 충분히 작을 경우 시간복잡도가 O(N)으로 수렴하는

 

무시무시한 효율을 자랑한다.

 

하지만 정렬의 특성상 배열을 사용한다는 점, 따라서 정수형의 경우에만 정렬이 가능하다는 점과 확보 가능한 메모리의

 

상한선이 정해져 있다는 것, 최댓값의 크기만 한 배열을 만들어야 해서 공간 복잡도가 늘어나는 것 등이 단점으로 작용해서

 

알고리즘 문제를 빠르게 풀어야 할 때가 아닌 실생활에선 퀵, 병합, 팀 정렬 등에 밀려 만나기 힘든 정렬이기도 하다.

 

물론 배열이랑 정수가 무슨 상관이 있느냐는 의문이 생길 수도 있다.

 

이는 알고리즘을 살피면서 자연스럽게 해결될 문제니까 일단 넘어간다.

 

Algorithm

 

카운팅 정렬은 크게 두 단계로 나뉜다.

 

1. 타깃 배열을 순회하며 원소 개수를 세어 이를 담은 Counting 배열을 만든 뒤 누적합 배열로 전환
2. 안정 정렬을 위해 타깃 배열의 마지막 원소부터 순회하며 Counting 배열을 근거로 정렬(Sort)

하나씩 나눠서 살펴보자

 

Step 1. Counting

 

해당 단계를 조금 구체적으로 나누면 아래와 같이 적을 수 있다.

 

• Target 배열의 최댓값을 크기로 갖는 Counting 배열 생성
• Target 배열을 순회하며 해당 원소 값을 Counting 배열의 인덱스로 삼아 Counting 배열의 원소 +1
  
  
  • 이 부분에서 정수밖에 정렬할 수 없는 특성이 요구된다. 타깃 배열의 원소 값을 인덱스로 사용해야 하기 때문이다.
• 순회가 끝나면 Counting 배열의 첫 인덱스부터 시작해서 해당 인덱스까지의 누적합으로 변환

말로 쓰니까 잘 와닿지 않는데, 이 부분을 그림으로 보면 아래와 같다.

 

너무 빠르지 않게 설정하긴 했지만, 만든 나도 몇 번이고 돌려보고 확실히 이해하긴 했다.

 

Step 1. Sorting

 

다음 단계는 정렬이다.

 

 

먼저 누적합으로 변경된 Counting 배열을 가만히 보면 해당 인덱스의 원소가 몇 번째 원소인지를 나타내고 있다.

 

배열은 1이 아닌 0부터 시작하기 때문에, 해당 원소 값에 -1을 해서 Result 배열의 인덱스를 찾아 넣어주면 된다.

 

이때 중복되는 원소가 기존 순서를 유지할 수 있도록(안정 정렬) Target 배열의 끝에서부터 순회하는 것이 좋으며,

 

-1 연산이 진행된 원소는 중복값의 정렬을 위해 변경된 값을 유지한다.

 

그림으로 보면 아래와 같다.

 

Implementation

 

이제 위의 그림을 코드로 옮겨보자.

 

특별히 재귀를 사용할 필요 없이 반복문 몇 개로 끝나는 간단한 정렬이다.

 

간단한 설명은 코드에 함께 표시해 두었다.

import java.util.Arrays;

public class CountingSort {

    private static int[] result;

    public static void main(String[] args) {

        int[] target = {4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0};

        countingSortImpl(target);

        System.out.println(Arrays.toString(result));
    }

    public static void countingSortImpl(int[] target) {

        int[] counting = new int[Arrays.stream(target).max().getAsInt() + 1];
        result = new int[target.length];

        for (int i = 0; i < target.length; i++) { // Counting
            counting[target[i]]++;
        }

        for (int i = 1; i < counting.length; i++) { // 누적 합
            counting[i] += counting[i - 1];
        }

        for (int i = target.length - 1; i >= 0; i--) { // 정렬
            counting[target[i]]--; // 해당 인덱스 값을 하나 줄여주고
            result[counting[target[i]]] = target[i]; // 줄여진 수를 인덱스 삼아 result에 값 채우기
        }
    }
}

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]

다음은 파이썬 구현이다.

target = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]


def counting_sort(target):
    counting = [0 for _ in range(max(target) + 1)]
    result = [0 for _ in range(len(target))]

    for i in range(len(target)):  # 리스트를 순회하며 요소 카운트 후 counting에 입력
        counting[target[i]] += 1

    for i in range(1, len(counting)):  # counting 리스트를 누적합 배열로 변환
        counting[i] += counting[i - 1]

    for i in range(len(target) - 1, -1, -1):  # 마지막 인덱스부터 거꾸로 순회
        counting[target[i]] -= 1  # 해당 인덱스의 값을 -1 해주고
        result[counting[target[i]]] = target[i]  # 줄어든 값을 인덱스로 삼아 result 리스트에 입력

    return result


print(counting_sort(target))

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]