파이썬으로 구현하는 카운팅 정렬(Counting Sort) 프로그램

이 글에서는 카운팅 정렬(Counting Sort) 알고리즘을 파이썬으로 구현하는 방법을 단계별로 살펴보겠습니다.

문제 정의

문제: 주어진 배열을 카운팅 정렬 개념을 활용하여 오름차순으로 정렬해야 합니다.

카운팅 정렬은 특정 범위 내의 키(key)를 대상으로 동작하는 정렬 기법입니다. 서로 다른 키와 값을 가지는 객체의 개수를 먼저 세고(count), 이후 간단한 산술 계산을 통해 각 객체가 출력 배열에서 차지할 위치를 결정하여 최종 결과를 출력합니다.

이 알고리즘은 비교 연산 없이 정렬을 수행하기 때문에, 데이터 값의 범위가 제한적일 때 시간 복잡도 O(n+k)(n은 요소 개수, k는 값의 범위)로 매우 효율적으로 동작한다는 장점이 있습니다.

그럼 아래 예제 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

구현 예제

def countSort(arr):
    # 정렬된 결과를 저장할 출력 배열
    output = [0 for i in range(256)]
    # 0으로 초기화된 카운트 배열 생성
    count = [0 for i in range(256)]
    # 문자열은 불변(immutable)이므로 리스트로 준비
    ans = ["" for _ in arr]

    # 각 문자의 등장 횟수를 카운트
    for i in arr:
        count[ord(i)] += 1

    # 누적 합계로 출력 배열 내 위치 계산
    for i in range(256):
        count[i] += count[i-1]

    # 출력 배열에 문자 배치
    for i in range(len(arr)):
        output[count[ord(arr[i])]-1] = arr[i]
        count[ord(arr[i])] -= 1

    # 정렬된 문자들로 최종 배열 구성
    for i in range(len(arr)):
        ans[i] = output[i]

    return ans

# 메인 실행부
arr = "Tutorialspoint"
ans = countSort(arr)
print("정렬된 문자 배열: " + str("".join(ans)))

실행 결과

정렬된 문자 배열: Taiilnooprsttu

코드 동작 원리

위 코드의 핵심 로직을 정리하면 다음과 같습니다.

1단계 — 카운트: 입력 문자열의 각 문자를 ord() 함수로 아스키 코드 값으로 변환한 뒤, 해당 인덱스의 카운트 배열 값을 1씩 증가시킵니다.

2단계 — 누적 합계: 카운트 배열의 각 값을 이전 값과 더하여 누적 합계를 만듭니다. 이를 통해 각 문자가 정렬 결과에서 위치할 마지막 인덱스를 알 수 있습니다.

3단계 — 배치: 입력 배열을 순회하면서 각 문자를 누적 합계가 가리키는 위치에 배치하고, 해당 카운트 값을 1 감소시켜 중복 문자도 올바르게 처리합니다.

모든 변수는 지역 스코프(local scope) 내에서 선언되며, 실행 흐름에 따라 각 변수의 참조 관계를 확인할 수 있습니다.

마무리

이번 글에서는 파이썬으로 카운팅 정렬을 구현하는 방법을 알아보았습니다. 카운팅 정렬은 비교 기반 정렬(O(n log n))보다 빠를 수 있지만, 값의 범위(k)가 클 경우 메모리 사용량이 증가한다는 점을 고려하여 상황에 맞게 활용하는 것이 좋습니다.