계수 정렬

다음의 5이하 자연수 데이터들을 오름차순 정렬하시오

> 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

 

이번이는 데이터가 30개이다. 다만 모든 데이터가 1부터 5 사이에 속한다는 특징이 있다. 이처럼 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 이 알고리즘의 속도는 무려 O(N)이다. 계수 정렬은 단순하게 크기를 기준으로 세는 알고리즘이다.

 

계수 정렬

데이터의 크기 별로 갯수를 세고 갯수만큼 각 데이터를 출력하면 정렬이 이루어진다.

 

#include<bits/stdc++.h>
using namespace std;

int main(){
	int temp;
	int count[5];
	int arr[30] = {
		1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
		3, 4, 4, 3, 5, 1, 2, 3, 5, 3,
		3, 1, 4, 3, 5, 1, 2, 1, 1, 1
	};
	for(int i=0; i<5; i++)
		count[i] = 0;
	
	for(int i=0; i<30; i++)
		count[arr[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)으로 빠르다고 할 수 있다.