카운팅 정렬(Counting Sort)

목표

카운팅 정렬 정의 설명

과정 설명

구현

시간복잡도와 공간복잡도 계산

정의

여타 다른 정렬 알고리즘이 비교 기반이라면 카운팅 정렬은 그와 다르게 갯수를 세어서 정렬한다.  말 그대로 카운팅을 통해 정렬을 하는 것이다.

과정

1. n개의 배열를 차례대로 돌면서 해당 값을 인덱스로 하는 배열에 1을 더한다.

2. 갯수가 저장된 배열을 체크한다.

3. 체크한 배열의 값이 0이 아니면 0이 될 때까지 출력한다.

구현

#include <iostream>
using namespace std;
int arr[10001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        int num;
        cin >> num;
        arr[num]++;
    }
    for(int i=1; i<10001; i++)
    {
        if(arr[i] == 0)
            continue;
        while(arr[i] != 0)
        {
            cout << i << '\n';
            arr[i]--;
        }
    }
    return 0;
}

시간복잡도와 공간복잡도 계산

시간복잡도: O(n+k)이다.

n은 정렬할 배열의 갯수이고, k는 정렬할 수 중 가장 큰 값이다.

만약 n이 k보다 크다면 O(n)이다.

 

공간복잡도: O(k)이다.

가장 큰 값만큼 배열을 필요로 하기 때문이다. 하지만 이러한 경우 공간복잡도의 낭비가 매우 심하기 때문에 다른 방법을 적용한다.

 

 

그렇기에 알파벳같이 정렬할 갯수가 정해져 있는 경우 매우 효율적으로 정렬할 수 있다. 하지만 최대 크기가 작은 경우에도 0과 1000만 사용된다면 1~999까지의 배열이 낭비되기 때문에 이러한 경우에는 최댓값이 작아도 적용하기에 부적합하다.

 

만약 음수가 있는 경우에는 0번 배열을 음수 중 가장 작은 수로 하여서 정렬하면 된다.