카운팅 정렬

카운팅 정렬은 정수형 데이터의 개수를 제어 정렬하는 알고리즘이다. 데이터의 최댓값(K)이 크지 않은 경우, O(N+K) 시간 복잡도로 매우 빠르게 정렬할 수 있다.

특징

• O(N+K)의 선형 시간 복잡도를 갖는다. K가 작을 때는 퀵정렬(O(N log N))보다 빠르다.
• 동일한 값이 많으면 정렬 속도가 더욱 빠르다.
• K가 클 경우, 메모리가 낭비된다.
• 음수 데이터 정렬이 어렵다.

카운팅 정렬 동작 원리

카운팅 정렬은 숫자의 등장 횟수를 저장한 후, 누적하여 정렬하는 방식이다.

동작 과정은 다음과 같다.
1. 입력 데이터의 최댓값(K) 크기의 배열을 생성한다.
2. 각 숫자가 등장한 횟수를 저장한다.
3. 누적 합을 구해 정렬된 위치를 결정한다.
4. 결과 배열에 값을 저장하여 정렬을 완료한다.

예제

def counting_sort(arr):
    max_value = max(arr)  # 배열에서 가장 큰 값 찾기
    count = [0] * (max_value + 1)  # 카운트 배열 생성

    # 각 숫자의 등장 횟수 세기
    for num in arr:
        count[num] += 1  

    # 정렬된 결과 저장할 리스트
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])  # 등장한 횟수만큼 추가

    return sorted_arr

# 테스트
arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # 출력: [1, 1, 2, 2, 4, 5, 7]