카운트 소트

#include<iostream>	
using namespace std;

int freq[2000001]; // 각 수의 등장 횟수를 저장하는 배열
int n;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);		
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		// ex) 2라는 정수를 입력받으면 2가 몇 번 나오는지 카운트 함
		// freq[2]의 의미는 2라는 정수가 몇 번 나왔는지의 횟수를 의미함
		// -백만을 해준 이유는 문제에서 -백만의 값이 주어질 수 있기 때문에 인덱스를 양수로 변환
		// freq[-백만] -> 인덱스에는 음수가 불가능하기 때문에 문제에서 가장 작은 음수값이 주어졌을 때 0이 되는 값을 더해줘야됨
		freq[a + 1000000]++; 
	}

	// -백만 <= a <= 백만 
	// 오름차순 정렬이기 때문에 가장 작은 수의 횟수부터 카운팅 한다
	for (int i = 0; i < 20000001; i++) {
		// 해당 수가 카운트 된 경우만 체크
		while (freq[i]--) {
			// 백만을 더했으니까 백만을 빼서 원래 수를 추출
			cout << i - 1000000 << '\n';
		}
	}
	
	return 0;
}

 

1. 메모리 사용량 

정렬하려는 값의 범위가 매우 크면, 값을 저장하기 위한 메모리 공간도 커지기 때문에 메모리 공간이 부족해지는 문제가 발생 할 수 있다. 

 

2. 범위가 큰 경우 비효율적으로 동작할 가능성

정렬하기 위해 주어진 값의 범위가 큰 경우, 실제로 사용되는 값이 적더라도 모든 범위에 대해 메모리를 할당해야 된다. 

예를 들어, 값이 1과 1억 사이에 2개만 있어도, 1에서 1억 까지의 모든 값을 위한 공간을 할당해야 된다.