Home 정렬 알고리즘(계수 정렬)
Post
Cancel

정렬 알고리즘(계수 정렬)

계수 정렬 (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. 최종 리스트에 담긴 횟수만큼 기록하고 리스트의 첫번째 데이터부터 그 값만큼 인덱스를 출력

CountingSort

구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}

출력

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

해설


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

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

    1
    
     vector<int> temp(max);
    
  2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스에 데이터를 1씩 증가

    1
    2
    
     for(int i=0; i < arr.size(); i++)
         temp[arr[i]] += 1;  
    
  3. 최종 리스트에 담긴 횟수만큼 기록하고 리스트의 첫번째 데이터부터 그 값만큼 인덱스를 출력

    1
    2
    3
    4
    
    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. 정렬 알고리즘

This post is licensed under CC BY 4.0 by the author.