[기초] C++ 알고리즘 : 계수 정렬 (Counting Sort)

---

 

계수정렬은 정수나 특정 범위의 정수를 정렬할 때 사용할 수 있는 매우 빠른 알고리즘입니다.

이 방법은 비교를 하지 않고 정렬을 수행합니다.

대신, 각 숫자가 몇 번 등장하는지 세어서 배열을 정렬합니다.

그렇기 때문에, 계수정렬의 시간복잡도는 O(n + k)로 매우 효율적입니다.

여기서 n은 리스트의 길이이고, k는 입력 값의 범위입니다.

 

---

 

#include <iostream>

void countingSort(int arr[], int n) {
    // 배열에서 최대값 찾기
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    // 카운트 배열 초기화
    int* count = new int[max_val + 1](); // +1 to include max_val itself

    // 각 요소의 출현 횟수 세기
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 배열 재구성
    int index = 0;
    for (int i = 0; i <= max_val; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    // 메모리 해제
    delete[] count;
}

// 배열을 출력하는 함수
void print(int arr[], int n) {
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

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

    std::cout << "정렬 전 배열: ";
    print(arr, n);

    // 계수 정렬 실행
    countingSort(arr, n);

    std::cout << "정렬 후 배열: ";
    print(arr, n);

    return 0;
}

 

출력 결과

 

정렬 전 배열: 4 2 2 8 3 3 1 
정렬 후 배열: 1 2 2 3 3 4 8

 

 

이 예제에서는 배열 'arr'를 정렬하기 위해 'countingSort' 함수를 사용합니다.

우선 배열에서 최대값을 찾아 그 크기만큼 'count' 배열을 생성하고,

'arr'의 각 요소를 카운트합니다.

그 후, 카운트된 값을 기반으로 원래 배열을 다시 채워 정렬합니다.

마지막에는 동적으로 할당받은 'count' 배열의 메모리를 해제합니다.

이 코드는 0 이상의 정수에 대해 효과적으로 작동합니다.

만약 음수를 포함하는 배열을 정렬해야 한다면,

전처리 단계에서 모든 값을 양수로 변환하는 추가 작업이 필요할 수 있습니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀