[Algorithm] 계수 정렬(Counting Sort)

계수 정렬이란?

범위 조건이 있을 때, 매우 빠른 정렬 알고리즘이다. 크기를 기준으로 갯수를 세는 방법이다.

예를 들어 1 3 1 5 1 3 4 4 7 가 있을 때, 1의 개수를 세서 정렬, 2의 개수를 세서 정렬... 이런식으로 하는 것이다.

#include <stdio.h>
#include <iostream>

using namespace std;

// 주어진 5이하의 자연수 데이터를 오름차순 정렬하는 문제
int main(void) {
    int temp;
    int count[5] = {0}; // 주어진 숫자들이 1, 2, 3, 4, 5 이기 때문에 5칸의 배열을 만들어줌 
    
    // 정렬할 자연수 데이터들 
    int array[30] = {
        1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
        3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
        3, 1, 4, 3, 5, 1, 2, 1, 1, 1
    };

    for(int i=0; i<30; i++){
        count[array[i]-1]++; //각 숫자별 카운트 
    }

    // 각 갯수만큼 출력 
    for(int i=0; i<5; i++){
        if(count[i] != 0){
            for(int j=0; j<count[i]; j++){
                cout << i+1 << ' ';
            }
        }
    }

    return 0;
} 

시간복잡도

모든 데이터의 크기를 메모리에 표현만 할 수 있다면, 각 데이터당 한 번씩만 접근하기 때문에 시간복잡도는 O(N)이다.

reference: https://www.youtube.com/watch?v=n4kbFRn2z9M&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=12