계수 정렬 (Counting Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

계수 정렬 총 정리

 

 

 

1. 계수 정렬이란?

계수 정렬은 비교 기반이 아닌 정렬 알고리즘으로, 정수 또는 정수로 표현 가능한 데이터의 빈도를 기반으로 정렬합니다. 값의 크기가 제한된 경우 매우 효율적이며, 주로 숫자 범위가 제한적이고 데이터가 중복이 많은 경우에 사용됩니다.

---

 

 

2. 원리

1. 정렬할 데이터의 범위를 파악하여 해당 범위의 크기만큼의 카운팅 배열을 생성합니다.
2. 데이터의 각 값을 인덱스로 하여 카운팅 배열에 빈도를 저장합니다.
3. 카운팅 배열을 누적 합으로 변환하여 정렬된 위치를 결정합니다.
4. 원본 배열을 순회하며 데이터를 정렬된 위치에 삽입합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [4, 2, 2, 8, 3, 3, 1]

1. 카운팅 배열 생성:
   • 데이터의 최대값 8을 기준으로 크기 9의 카운팅 배열 생성(데이터 크기 범위가 [0,8]이니까) : [0, 0, 0, 0, 0, 0, 0, 0, 0]
   • 각 데이터를 카운팅: [0, 1, 2, 2, 1, 0, 0, 0, 1]
   • 1이 1개, 2가 2개, 3이 2개, 4가 1개, 5는 없음, 6도 없음, 7도 없음, 8은 1개
2. 누적 합 계산:
   • 카운팅 배열을 누적 합으로 변환: [0, 1, 3, 5, 6, 6, 6, 6, 7]
3. 정렬된 배열 생성:
   • 원본 배열을 역순으로 순회하며 데이터를 정렬된 위치에 삽입:
     • 1 → 위치 0 → [1, _, _, _, _, _, _]
     • 3 → 위치 4 → [1, _, _, _, 3, _, _]
     • 3 → 위치 3 → [1, _, _, 3, 3, _, _]
     • 8 → 위치 6 → [1, _, _, 3, 3, _, 8]
     • 2 → 위치 2 → [1, _, 2, 3, 3, _, 8]
     • 2 → 위치 1 → [1, 2, 2, 3, 3, _, 8]
     • 4 → 위치 5 → [1, 2, 2, 3, 3, 4, 8]
4. 정렬 완료:
   • 최종 배열: [1, 2, 2, 3, 3, 4, 8]

반응형

---

 

 

4. 시간 복잡도

• 시간 복잡도: O(n + k)
  • n: 데이터의 개수
  • k: 데이터 값의 범위
• 공간 복잡도: O(n + k)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>
#include <string.h>

void countingSort(int arr[], int n, int max) {
    int count[max + 1];
    int output[n];

    memset(count, 0, sizeof(count));

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = 8;

    countingSort(arr, n, max);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

Java 코드

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr, int max) {
        int[] count = new int[max + 1];
        int[] output = new int[arr.length];

        for (int num : arr) {
            count[num]++;
        }

        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        System.arraycopy(output, 0, arr, 0, arr.length);
    }

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

        countingSort(arr, max);
        System.out.println(Arrays.toString(arr));
    }
}

 

Python 코드

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for num in arr:
        count[num] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

---

 

 

6. 주의점

1. 계수 정렬은 정수 또는 정수로 표현 가능한 데이터에만 사용 가능합니다.
2. 데이터의 최대값이 너무 클 경우 공간 복잡도가 증가합니다.

---

 

 

7. 장단점

장점

• 매우 빠른 성능 (O(n + k))을 제공.
• 데이터의 크기와 개수가 적당하면 효율적임.

단점

• 데이터 범위가 크면 비효율적.
• 비교 기반 정렬 알고리즘이 아니기 때문에 범용성이 떨어짐.

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주