계수 정렬 (Counting Sort)

개yo

---

이번 포스팅에선 계수정렬 (Counting Sort)에 대해 알아볼 것이다. 계수 정렬은 지난 정렬 알고리즘과 다르게 특정 조건에서 매우 빠르게 작동하는 정렬 알고리즘이다. 앞선 정렬 알고리즘의 시간 복잡도는 대개 O(N^2), O(N * log N) 의 형태를 띄었지만 오늘 알아볼 계수정렬의 시간 복잡도는 O(N + K)를 보장한다. 물론 데이터의 상태가 최악이여도 말이다 : )

문제

---

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

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

SOL

1. 가장 작은 ~ 큰 데이터가 담길 리스트를 생성

2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스에 데이터를 1씩 증가

3. 최종 리스트에 담긴 횟수만큼 기록하고 리스트의 첫번째 데이터부터 그 값만큼 인덱스를 출력

구현

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 

void solution(vector<int> arr, int max)
{
    // 모든 범위의 배열 선언 
    vector<int> temp(max);
    vector<int> answer;
    // 각 데이터에 해당하는 인덱스값 증가
    for(int i=0; i < arr.size(); i++)
        temp[arr[i]] += 1;            
    for(int i=0; i <= max; i++)
        if(temp[i] != 0)
            for(int j=0; j < temp[i]; j++)
                answer.push_back(i);
    for(auto el : answer)
        cout << el << " ";
    cout << endl;
}

int main()
{
    vector<int> arr{7,5,9,0,3,1,6,2,9,1,4,8,0,5,2};

    int max(9);
    solution(arr, max);

    return 0;
}

출력

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

해설

---

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

1. 가장 작은 ~ 큰 데이터가 담길 리스트를 생성

    vector<int> temp(max);

2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스에 데이터를 1씩 증가

   for(int i=0; i < arr.size(); i++)
       temp[arr[i]] += 1;  

3. 최종 리스트에 담긴 횟수만큼 기록하고 리스트의 첫번째 데이터부터 그 값만큼 인덱스를 출력

   for(int i=0; i <= max; i++)
       if(temp[i] != 0)
           for(int j=0; j < temp[i]; j++)
               answer.push_back(i);

마무리

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N + K)이다.
• 계수 정렬은 특정 데이터에 극심하게 비효율성을 띈다
  • ex) 데이터가 0 ~ 999.999의 범위를 가진 단 2개만 존재 할 경우
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장 할 때 효과적으로 사용할 수 있다.
  • ex) 성적의 경우 100점을 맞은 학생이 여러명이 있을 수 있기 때문에 계수 정렬이 효과적이다.

---

Reference

---

(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘