7. 계수 정렬 (Counting Sort)

 

#include <iostream>
using namespace std;

int main() {
	int arr[12] = { 1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4 };
	int cnt[5] = { 0 }; //원소의 범위만큼만 정의한다
	int N = 12, cnt_len = 5;
	
	//계수 정렬
	for (int i = 0; i < N; i++) cnt[arr[i] - 1]++; //원소의 크기에 따른 개수 카운트

	for (int i = 0; i < cnt_len; i++) {
		while (cnt[i] != 0) {
			cout << i + 1 << "\n";
			cnt[i]--;
		}
	}

	return 0;
}