[알고리즘] 계수 정렬 (Counting Sort)

계수 정렬: 크기를 기준으로 개수를 세어 정렬

→ 위치를 바꿔가며 정렬하는 것이 아님

 

시간 복잡도: O(N)  (모든 데이터의 크기 범위를 메모리 상에 표현할 수 있다면)

 

#include <iostream>
#include <algorithm>

using namespace std;



int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	cin.sync_with_stdio(false);
	
	int cnt[11] = { 0 };
	int arr[] = { 1,5,8,4,6,9,5,5,1,3,2,4,7,8,2,4,1,1,7,10 };

	for (int i = 0; i < 20; i++) {
		cnt[arr[i]]++;
	}
	for (int i = 1; i <= 10; i++) {
		if (cnt[i] != 0) {
			for (int j = 1; j <= cnt[i]; j++) {
				cout << i << " ";
			}
		}
	}
}