[CH6 정렬] 기준에 따라 데이터를 정렬 (5)

계수 정렬

• 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다
• 이는 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다
• 모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N개고 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다
• 계수 정렬은 매우 빠르게 동작할 뿐만 아니라 원리도 간단하다
• 계수 정렬은 크기 범위가 제한되어 정수 형태로 표현 가능할 때만 사용할 수 있으므로 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하다
• 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문에, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬을 사용할 수 없다
• 계수 정렬은 앞서 다룬 알고리즘과 달리 직접 데이터의 값을 비교한 뒤 위치를 변경하며 정렬하는 비교 기반의 정렬 알고리즘이 아니다
• 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다

 

만약 아래와 같은 데이터를 계수 정렬 알고리즘으로 정렬한다고 해보자

계수정렬 예시

가장 큰 데이터는 9, 가장 작은 데이터는 0이므로, 정렬할 데이터의 범위는 0~9이다

따라서 리스트의 인덱스가 모든 범위를 포함할 수 있도록 크기가 10인 리스트를 선언하고 모두 0이 되도록 초기화한다

그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다

쉽게 말해서 데이터들의 개수를 세서 리스트에 넣으면 되는 것이다!

 

계수 정렬 결과

그러면 위처럼 전체 데이터의 개수를 리스트에 넣는다

그리고 이를 처음부터 반복하며 개수만큼 출력하면 되는 것이다

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

---

계수 정렬 알고리즘 소스코드

 

파이썬 코드)

#모든 원소의 값이 0보자 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i ,end=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

C++ 코드)

#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 << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        }
    }
}

 

---

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값을 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+M)이다

계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 증가시키고, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때무이다

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있고, 항상 빠르게 동작한다

보통 기수 정렬은 계수 정렬에 비해 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다

 

 

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다

예를 들어 데이터가 9과 999999 두 개만 존재한다고 하면, 리스트는 0부터 999999까지 쟁쳐야한다

즉, 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다

계수 정렬의 공간 복잡도는 O(N+K)이다