Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 카운팅 정렬(Counting Sort) 프로그램

카운팅 정렬(Counting Sort)은 안정 정렬(stable sort) 방식의 정렬 기법으로, 키 값이 작은 숫자 범위에 속하는 데이터를 정렬할 때 주로 사용됩니다. 이 알고리즘은 같은 키 값을 가진 데이터의 개수를 직접 세어(count) 그 정보를 활용해 정렬된 결과를 만들어냅니다. 정렬 대상 키 값들 사이의 차이가 크지 않을 때 매우 효율적으로 동작하지만, 키의 범위가 지나치게 넓으면 카운트 배열로 인해 공간 복잡도가 크게 늘어날 수 있다는 점에 유의해야 합니다.

카운팅 정렬의 작동 원리

  1. 배열에서 최대값을 찾고, 그 크기(max+1)만큼의 카운트 배열을 준비합니다.
  2. 배열을 한 번 순회하면서 각 값이 등장한 횟수를 카운트 배열에 기록합니다.
  3. 카운트 배열을 누적합으로 변환하면 각 값이 정렬 결과에서 차지할 위치를 알 수 있습니다.
  4. 원본 배열을 뒤에서부터 순회하며 출력 배열의 올바른 자리에 원소를 하나씩 배치합니다.

뒤에서부터 순회하기 때문에 값이 같은 원소들의 상대적인 순서가 유지되는데, 이것이 바로 카운팅 정렬이 안정 정렬이라 불리는 이유입니다.

카운팅 정렬의 복잡도

  • 시간 복잡도: O(n+r) — n은 데이터 개수, r은 최대 키 값

  • 공간 복잡도: O(n+r)

입력 − 정렬되지 않은 데이터 목록: 2 5 6 2 3 10 3 6 7 8
출력 − 정렬 후 배열: 2 2 3 3 5 6 6 7 8 10

알고리즘

countingSort(array, size)

입력: 데이터 배열과 배열 내 전체 원소 개수

출력: 정렬된 배열

Begin
    max ← 배열에서 최대값을 구한다.
    크기가 [max+1]인 카운트 배열을 선언한다.
    for i := 0 to max do
        count[i] = 0 // 카운트 배열의 모든 요소를 0으로 초기화
    done
    for i := 1 to size do
        배열에서 발견된 각 숫자의 등장 횟수를 카운트 배열에 누적한다.
    done
    for i := 1 to max do
        count[i] = count[i] + count[i-1] // 누적 빈도(cumulative frequency)를 계산한다.
    done
    for i := size downto 1 do
        출력 배열의 해당 위치에 숫자를 저장한다.
        count[숫자] 값을 1 감소시킨다.
    done
    출력 배열을 반환한다.
End

C++ 예제 코드

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i<=size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int getMax(int array[], int size) {
    int max = array[1];
    for(int i = 2; i<=size; i++) {
        if(array[i] > max)
            max = array[i];
    }
    return max; // 배열에서 최대값을 반환
}

void countSort(int *array, int size) {
    int output[size+1];
    int max = getMax(array, size);
    int count[max+1];      // 카운트 배열 생성 (max+1개의 요소)
    for(int i = 0; i<=max; i++)
        count[i] = 0;      // 카운트 배열을 모두 0으로 초기화
    for(int i = 1; i <= size; i++)
        count[array[i]]++; // 배열의 각 숫자 등장 횟수 증가
    for(int i = 1; i<=max; i++)
        count[i] += count[i-1]; // 누적 빈도 계산
    for(int i = size; i>=1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1; // 같은 숫자의 카운트 감소
    }
    for(int i = 1; i<=size; i++) {
        array[i] = output[i]; // 출력 배열을 원본 배열에 복사
    }
}

int main() {
    int n;
    cout << "원소 개수를 입력하세요: ";
    cin >> n;
    int arr[n+1];       // 입력받은 개수만큼 배열 생성
    cout << "원소를 입력하세요:" << endl;
    for(int i = 1; i<=n; i++) {
        cin >> arr[i];
    }
    cout << "정렬 전 배열: ";
    display(arr, n);
    countSort(arr, n);
    cout << "정렬 후 배열: ";
    display(arr, n);
}

참고: 위 코드는 배열 크기를 변수로 지정하는 가변 길이 배열(VLA)을 사용하므로, GCC처럼 VLA를 지원하는 컴파일러로 컴파일해야 합니다. 표준 C++ 환경에서는 new 연산자나 std::vector를 사용해 배열을 동적으로 생성하는 것이 좋습니다.

실행 결과

원소 개수를 입력하세요: 10
원소를 입력하세요:
2 5 6 2 3 10 3 6 7 8
정렬 전 배열: 2 5 6 2 3 10 3 6 7 8
정렬 후 배열: 2 2 3 3 5 6 6 7 8 10