Major/Algorithms

[이취코] ch06-4. 계수 정렬 (Count Sort)

마이구미포포 2022. 5. 3. 11:54

계수 정렬 (Count Sort)
: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

계수 정렬은 다른 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 알고리즘)이 아니다
계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다

예시를 통해서 알아보도록 하자

초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

초기 데이터가 이렇게 있다고 해보자

먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 담길 수 있는 리스트를 선언한다
여기서 가장 큰 데이터가 9 이고 가장 작은 데이터가 0 이므로 모두 담을 수 있는 크기가 10 인 리스트를 선언하면 된다

계수정렬에서 데이터의 값은 새로 선언한 리스트의 인덱스와 같다고 보면 된다
처음에 만든 리스트를 모두 0으로 초기화하고, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 된다


[STEP 1]  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 1 0 0

여기서 처음 데이터의 값이 7이므로 리스트의 인덱스가 7인 데이터 값을 1 증가시킨다


[STEP 2]  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 1 0 1 0 0



[STEP 3]  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 1 0 1 0 1

이 과정을 반복하면

[STEP 14]  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
2 2 1 1 1 2 1 1 1 2

 

[STEP 15]  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
2 2 2 1 1 2 1 1 1 2

 

리스트가 이렇게 완성되고, 이 리스트에는 각 인덱스의 수가 몇 번 들어있는지 횟수가 기록된다
예를 들어, 인덱스 5의 값이 2 이므로 5는 정렬에서 두 번 등장한 것이다

따라서 이 리스트 자체가 정렬된 상태라고 볼 수 있고, 확인하려면 이 리스트를 순서대로 출력만 하면 된다

코드

#include <iostream>
#define MAX_VALUE 9

using namespace std;

int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];

int main(void) {
    for (int i = 0; i < n; i++) {
        cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
    }
    for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        }
    }
}

배열, 리스트를 선언해주고 리스트의 크기는 배열의 최댓값에서 +1 해주면 된다
반복문을 통해 데이터에 해당하는 인덱스의 값을 증가시켜주고
마지막에 출력하면 정렬된 배열을 볼 수 있다

계수 정렬 특징

앞에서 말했듯이 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 사용한다면 매우 빠르다

모든 데이터가 양의 정수라고 가정해보자
데이터의 개수가 N이고 데이터중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 만족한다
이처럼 계수정렬은 빠르고 원리도 간단하다

하지만 계수정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때'만 사용 가능하다
데이터의 값이 무한대이거나 실수형 데이터일 경우 사용할 수 없다

그러한 이유는 계수 정렬을 이용할 때  ' 데이터의 모든 범위를 담을 수 있는 리스트를 선언' 해야하기 때문이다
따라서 데이터의 가장 작은 값과 가장 큰 값의 차이가 큰 경우 (ex. 1,000,000을 넘어가는 경우) 에는 효과적이지 않다

시간복잡도

앞서 언급했듯이 계수 정렬의 시간 복잡도는 데이터의 개수가 N이고 데이터중 최댓값이 K일 때, O(N+K)이다
앞에서부터 데이터를 하나씩 확인하면서 리스트에서 인덱스의 값을 1씩 증가시켜야하고,
나중에 인덱스의 값을 확인할 때 데이터의 최댓값의 크기만큼 반복해햐하기 때문이다

공간복잡도

계수 정렬은 리스트를 따로 선언하기 때문에 데이터의 크기가 크면 퀵 정렬을 이용하는 것이 유리하다
즉 계수 정렬은 데이터의 크기가 한정되어있고, 데이터의 크기가 중복되어 있을 수록 유리한 것이다
계수 정렬의 복잡도는 O(N+K) 이다

저작자표시