Counting Sort(계수 정렬)

 카운팅 정렬(Counting Sort)은 특정 조건에서 매우 효율적인 정렬 방식을 제공하는 비교 기반 정렬이 아닌 알고리즘입니다. 그 특징과 구현에 대해 자세히 설명하겠습니다.

Counting Sort란?

카운팅 정렬은 입력 배열에서 각 요소의 등장 횟수를 세고, 그 카운트를 기반으로 배열을 정렬하는 알고리즘입니다. 이 방법은 특히 배열의 원소가 특정 범위 내의 정수일 때 매우 효과적입니다. 이 정렬은 추가적인 메모리 공간을 사용해 입력 원소의 빈도 수를 카운팅하며, 이 정보를 이용하여 출력 배열을 직접 생성합니다.

Counting Sort 사이클 설명

카운팅 정렬의 주요 사이클은 다음과 같은 단계로 이루어집니다:

1. 카운팅 배열 초기화: 입력 배열의 각 요소 값에 대응하는 인덱스를 가진 카운팅 배열을 초기화합니다.
2. 요소 카운팅: 입력 배열을 순회하면서 각 요소가 나타난 횟수를 카운팅 배열에 기록합니다.
3. 누적 카운트 계산: 카운팅 배열의 각 요소를 그 이전 요소들의 합으로 갱신하여, 각 요소의 최종 위치를 결정합니다.
4. 결과 배열 생성: 입력 배열을 다시 순회하면서, 각 요소를 카운팅 배열에서 지정된 위치에 배치하고, 카운팅 배열을 갱신합니다.

Counting Sort 시간복잡도와 공간복잡도

• 시간 복잡도:
  • 모든 경우: 𝑂(𝑛+𝑘) - 여기서 𝑛은 배열의 크기, 𝑘는 입력 범위의 크기입니다. 𝑘가 𝑛과 비슷하거나 작을 때 가장 효율적입니다.
• 공간 복잡도:
  • 𝑂(𝑘) - 카운팅 배열을 저장하기 위한 추가 공간이 필요합니다. 𝑘가 매우 클 경우, 카운팅 정렬은 메모리 사용량이 많아 비효율적일 수 있습니다.

Counting Sort 장단점

장점:

• 빠른 정렬 속도: 𝑛과 𝑘의 값이 비교적 작을 때 매우 빠르게 동작합니다.
• 안정 정렬: 같은 값을 가진 원소들의 상대적 순서가 유지됩니다.

단점:

• 메모리 사용량: 𝑘가 매우 클 경우 많은 메모리를 필요로 합니다.
• 제한된 사용: 정수나 특정 범위 내의 데이터에만 적용 가능하며, 부동 소수점 같은 타입에는 적합하지 않습니다.

Counting Sort Code (Java, Golang, Python)

Java:

public class CountingSort {
    void sort(int[] arr) {
        int n = arr.length;
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        int[] output = new int[n];

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

        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]]--;
        }

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

 

Golang:

package main

import (
    "fmt"
)

func CountingSort(arr []int) {
    max := 0
    for _, value := range arr {
        if value > max {
            max = value
        }
    }

    count := make([]int, max+1)
    output := make([]int, len(arr))

    for _, value := range arr {
        count[value]++
    }

    for i := 1; i <= max; i++ {
        count[i] += count[i-1]
    }

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

    copy(arr, output)
    fmt.Println("Sorted array is:", arr)
}

func main() {
    sample := []int{4, 2, 2, 8, 3, 3, 1}
    CountingSort(sample)
}

 

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 i in reversed(range(len(arr))):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1

    for i in range(len(arr)):
        arr[i] = output[i]

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
counting_sort(arr)
print("Sorted array:", arr)

 

sort