카운팅 정렬 (Counting Sort)

2017. 5. 19. 02:05알고리즘/알고리즘

반응형

Counting Sort


카운팅 정렬은 반복되는 숫자가 있으면서 숫자의 범위가 너무 크지않을 때 유용하다.


순서

1. 숫자의 범위만큼 배열을 선언해주고 0으로 초기화한다.

2. Data의 숫자를 하나씩 꺼내면서 카운트를 세준다.

3. 처음에 선언한 배열에서 카운트가 0이 아닌 숫자들을 카운트 만큼 출력해주면 된다.





소스 코드


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
/*
           카운팅 정렬            
 중복된 수를 정렬할때 유용         
 숫자의 범위가 한정적일때 유용     
*/
 
#include <iostream>
using namespace std;
 
int main() {
    int n, num[10001];  // num안의 숫자는 최대 허용 숫자 범위
    for (int i = 0; i < 10001; i++) {  // 0으로 초기화 시켜주어야 나중에 카운팅할 수 있음.
        num[i] = 0;
    }
    ios::sync_with_stdio(false);  // 동기화 false  -> cin 속도 극대화
    cin >> n;
 
    for (int i = 0; i < n; i++) {    // 입력받는 수를 배열의 index로 입력받아 카운팅해준다.
        int a;
        cin >> a;
        num[a]++;
    }
 
    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < num[i]; j++) {
            cout << i << '\n';   // endl -> '\n'으로 써야 편함.
        }
    }
    return 0;
}
cs







반응형

'알고리즘 > 알고리즘' 카테고리의 다른 글

순열 알고리즘 (Permutation)  (0) 2017.07.18
조합 알고리즘 (Combination Algorithm)  (0) 2017.05.19
병합 정렬 (Merge sort)  (0) 2017.05.19
유클리드 호제법  (0) 2017.05.18