범위 한정될 때 유리한 계수 정렬

계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘과 달리 데이터의 크기 범위가 한정되어 있을 때 매우 빠른 성능을 발휘하는 알고리즘입니다. 이 글에서는 계수 정렬의 원리, 구현 방법, 시간/공간 복잡도, 그리고 장단점에 대해 자세히 알아보겠습니다. 계수 정렬의 원리 계수 정렬은 정렬 대상이 되는 데이터들이 모두 정수이며, 그 범위가 제한적일 경우 효과적입니다. 작동 원리: 입력 배열에 존재하는 각 정수의 등장 횟수를 미리 세어 두고, 이 횟수를 이용하여 최종 정렬된 배열에서 각 숫자가 위치할 인덱스를 결정합니다. 비교 연산이 없음: 기존의 선택, 삽입, 퀵 정렬과 달리 서로 값을 비교하지 않고, 각 숫자가 몇 번 등장하는지를 기반으로 정렬을 수행합니다. 동작 과정 계수 정렬의 전형적인 동작 과정은 다음과 같습니다. 1. 최대값 및 최소값 확인: 배열의 전체 범위를 파악하기 위해 최대값(또는 최소값) 정보를 추출합니다. 2. 카운팅 배열 생성: 입력 배열의 값들이 모두 들어갈 수 있는 크기의 새로운 배열(카운팅 배열)을 생성한 후, 각 인덱스에 대응하는 값이 등장하는 횟수를 저장합니다. 3. 누적 합 계산: 카운팅 배열의 각 원소에 대해 누적합을 계산하여, 해당 값이 최종 정렬 배열에서 몇 번째 인덱스부터 배치되어야 하는지를 결정합니다. 4. 정렬 배열 생성: 입력 배열을 뒤에서부터 순회하면서, 누적합에 따른 위치에 값을 배치하고, 배치한 후에는 해당 카운트 값을 감소시킵니다. 코드 예제 (Python) 아래는 파이썬으로 구현한 계수 정렬의 예시입니다. 이 코드는 입력 배열의 값들이 0 이상의 정수이고, 최대값이 비교적 작은 경우에 유용하게 동작합니다. def counting_sort(arr): if not arr: return arr max_val = max(arr) # 카운팅 배열 생성 (0부터 max_val까지 모두 포함) count = [0] * (max_val + 1) # 각 원소의 등장 횟수를 기록 for num in arr: count[num] += 1 # 누적 합 계산: 각 인덱스가 최종 배열에서 시작할 위치를 결정 for i in range(1, len(count)): count[i] += count[i - 1] # 정렬된 결과를 저장할 배열 생성 sorted_arr = [0] * len(arr) # 원본 배열을 뒤에서부터 순회하면 안정적인 정렬이 가능하다. for num in reversed(arr): sorted_arr[count[num] - 1] = num count[num] -= 1 return sorted_arr # 예제 실행 arr = [4, 2, 2, 8, 3, 3, 1] print("정렬 전: ", arr) print("정렬 후: ", counting_sort(arr)) 이 코드는 먼저 각 수의 빈도수를 기록한 뒤, 누적합을 계산하여 정렬된 배열의 각 숫자 위치를 결정합니다. 시간 및 공간 복잡도 시간 복잡도: 입력 배열의 크기를 n, 데이터의 범위를 k라고 할 때, 계수 정렬은 $$O(n + k)$$의 시간 복잡도를 가집니다. 따라서 k가 n에 비해 작은 경우 매우 빠르게 동작합니다. 공간 복잡도: 별도의 카운팅 배열을 필요로 하므로 $$O(k)$$의 추가 공간이 필요합니다. 이 점은 데이터의 범위가 클 경우 단점으로 작용할 수 있습니다. 장점과 단점 아래 표는 계수 정렬의 장단점을 정리한 것입니다. 항목 장점 단점 시간 효율성 데이터 범위가 제한되어 있으면 매우 빠른 $$O(n)$$ 시간에 정렬 가능 k가 크면 시간 복잡도가 증가 안정성 동일한 값의 순서를 유지하는 안정 정렬 음수나 소수 같은 비정수 데이터에는 직접 적용 불가 구현의 단순성 알고리즘 구조가 단순하여 이해 및 구현이 용이 추가 메모리 사용으로 인한 공간 낭비 가능성 계수 정렬은 특히 학생 성적, 제한된 범위 내의 센서 데이터 등과 같이 데이터 범위가 제한된 경우에 탁월한 성능을 발휘합니다. 결론 계수 정렬은 데이터의 범위가 제한되어 있는 경우에 매우 유리한 정렬 알고리즘입니다. 입력 데이터 내에 값의 분포가 한정되어 있다면, 비교 기반 정렬보다 훨씬 빠르게 정렬 작업을 수행할 수 있습니다. 하지만, 데이터 범위가 너무 넓거나 음수, 실수 등 정수 이외의 값이 포함될 경우에는 다른 알고리즘과의 병행 적용이나 변형이 필요합니다. 오늘 글에서 소개한 내용과 코드 예제를 참고하여, 자신만의 정렬 솔루션에 계수 정렬을 적용해보시기 바랍니다. 이처럼 계수 정렬의 동작 원리와 효율성을 이해하면, 제한된 수 범위의 데이터 정렬 문제에서 적합한 해법을 찾는 데 큰 도움이 될 것입니다.

Mar 11, 2025 - 05:36

계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘과 달리 데이터의 크기 범위가 한정되어 있을 때 매우 빠른 성능을 발휘하는 알고리즘입니다. 이 글에서는 계수 정렬의 원리, 구현 방법, 시간/공간 복잡도, 그리고 장단점에 대해 자세히 알아보겠습니다.

계수 정렬의 원리

계수 정렬은 정렬 대상이 되는 데이터들이 모두 정수이며, 그 범위가 제한적일 경우 효과적입니다.

작동 원리: 입력 배열에 존재하는 각 정수의 등장 횟수를 미리 세어 두고, 이 횟수를 이용하여 최종 정렬된 배열에서 각 숫자가 위치할 인덱스를 결정합니다.
비교 연산이 없음: 기존의 선택, 삽입, 퀵 정렬과 달리 서로 값을 비교하지 않고, 각 숫자가 몇 번 등장하는지를 기반으로 정렬을 수행합니다.

동작 과정

계수 정렬의 전형적인 동작 과정은 다음과 같습니다.

1. 최대값 및 최소값 확인: 배열의 전체 범위를 파악하기 위해 최대값(또는 최소값) 정보를 추출합니다.
2. 카운팅 배열 생성: 입력 배열의 값들이 모두 들어갈 수 있는 크기의 새로운 배열(카운팅 배열)을 생성한 후, 각 인덱스에 대응하는 값이 등장하는 횟수를 저장합니다.
3. 누적 합 계산: 카운팅 배열의 각 원소에 대해 누적합을 계산하여, 해당 값이 최종 정렬 배열에서 몇 번째 인덱스부터 배치되어야 하는지를 결정합니다.
4. 정렬 배열 생성: 입력 배열을 뒤에서부터 순회하면서, 누적합에 따른 위치에 값을 배치하고, 배치한 후에는 해당 카운트 값을 감소시킵니다.

코드 예제 (Python)

아래는 파이썬으로 구현한 계수 정렬의 예시입니다. 이 코드는 입력 배열의 값들이 0 이상의 정수이고, 최대값이 비교적 작은 경우에 유용하게 동작합니다.

def counting_sort(arr):
    if not arr:
        return arr

    max_val = max(arr)
    # 카운팅 배열 생성 (0부터 max_val까지 모두 포함)
    count = [0] * (max_val + 1)

    # 각 원소의 등장 횟수를 기록
    for num in arr:
        count[num] += 1

    # 누적 합 계산: 각 인덱스가 최종 배열에서 시작할 위치를 결정
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 정렬된 결과를 저장할 배열 생성
    sorted_arr = [0] * len(arr)

    # 원본 배열을 뒤에서부터 순회하면 안정적인 정렬이 가능하다.
    for num in reversed(arr):
        sorted_arr[count[num] - 1] = num
        count[num] -= 1

    return sorted_arr

# 예제 실행
arr = [4, 2, 2, 8, 3, 3, 1]
print("정렬 전: ", arr)
print("정렬 후: ", counting_sort(arr))

이 코드는 먼저 각 수의 빈도수를 기록한 뒤, 누적합을 계산하여 정렬된 배열의 각 숫자 위치를 결정합니다.

시간 및 공간 복잡도

시간 복잡도: 입력 배열의 크기를 n, 데이터의 범위를 k라고 할 때, 계수 정렬은 $$O(n + k)$$의 시간 복잡도를 가집니다. 따라서 k가 n에 비해 작은 경우 매우 빠르게 동작합니다.
공간 복잡도: 별도의 카운팅 배열을 필요로 하므로 $$O(k)$$의 추가 공간이 필요합니다. 이 점은 데이터의 범위가 클 경우 단점으로 작용할 수 있습니다.

장점과 단점

아래 표는 계수 정렬의 장단점을 정리한 것입니다.

항목	장점	단점
시간 효율성	데이터 범위가 제한되어 있으면 매우 빠른 $$O(n)$$ 시간에 정렬 가능	k가 크면 시간 복잡도가 증가
안정성	동일한 값의 순서를 유지하는 안정 정렬	음수나 소수 같은 비정수 데이터에는 직접 적용 불가
구현의 단순성	알고리즘 구조가 단순하여 이해 및 구현이 용이	추가 메모리 사용으로 인한 공간 낭비 가능성

계수 정렬은 특히 학생 성적, 제한된 범위 내의 센서 데이터 등과 같이 데이터 범위가 제한된 경우에 탁월한 성능을 발휘합니다.

결론

계수 정렬은 데이터의 범위가 제한되어 있는 경우에 매우 유리한 정렬 알고리즘입니다. 입력 데이터 내에 값의 분포가 한정되어 있다면, 비교 기반 정렬보다 훨씬 빠르게 정렬 작업을 수행할 수 있습니다. 하지만, 데이터 범위가 너무 넓거나 음수, 실수 등 정수 이외의 값이 포함될 경우에는 다른 알고리즘과의 병행 적용이나 변형이 필요합니다. 오늘 글에서 소개한 내용과 코드 예제를 참고하여, 자신만의 정렬 솔루션에 계수 정렬을 적용해보시기 바랍니다.

이처럼 계수 정렬의 동작 원리와 효율성을 이해하면, 제한된 수 범위의 데이터 정렬 문제에서 적합한 해법을 찾는 데 큰 도움이 될 것입니다.