[알고리즘] Counting Sort

🐥 Counting Sort

counting sort는 정렬 알고리즘 중 가장 간단한 알고리즘으로 볼 수 있다. 그냥 각 수가 나오는 횟수를 세고, 그 횟수만큼 출력해주면 되기 때문이다.

아래 그림을 보면 더 잘 이해가 될 것이다.

위와 같은 리스트가 있다고 가정하자.

 

리스트에서 값이 1부터 6까지 나오기 때문에 해당 값이 몇번 나왔는지 배열에 저장하고 오름차순으로 횟수만큼 출력해주면 정렬이 되는 것을 볼 수 있다.

💥 단점

counting sort를 사용하기 위해서는 각 수가 나온 횟수를 저장해줘야 한다. 이는 미리 큰 테이블을 만들어두고 대응되는 원소의 값을 증가시키는 방식으로 구현이 가능하다.
예를들어 만약 나오는 수가 1부터 999까지라고 하면 int freq[1000] 와 같이 선언하여 사용하면 되는 것이다.
하지만 나오는 수가 굉장히 커지면 횟수를 저장하는 배열의 크기도 커져야하고, 이는 곧 메모리를 초과로 이어진다. 때문에 counting sort는 나오는 수가 한정적일 때만 사용이 가능한 알고리즘이다.
일반적으로 나오는 수가 1000만 이하일 때는 counting sort를 사용할 수 있다고 알아두자.

💻 구현

15688번: 수 정렬하기 5

위 문제를 해결하면서 counting sort에 대해 알아보자.

 

#include <iostream>
#define NORMAL 1000000
using namespace std;

int N, num;
int arr[2000002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	while (N--) {
		cin >> num;
		arr[num + NORMAL]++;
	}

	for (int i = 0; i < 2000002; i++) {
		while (arr[i] > 0) {
			cout << i - NORMAL << '\n';
			arr[i]--;
		}
	}

	return 0;
}

• 문제에서 절댓값이 1,000,000보다 작거나 같은 정수가 나온다고 했고, 수 자체를 배열의 index로 사용하기 위해 음수가 나오지 않도록 1,000,000값을 더해 index로 사용한다.
• 입력된 값을 index로 사용하여 arr 배열에 값이 나온 횟수를 증가시킨다.
• arr에는 (index - 1,000,000)이 나온 횟수를 저장하기 때문에 0보다 크다면 출력하고 개수를 줄여준다.
• 개수가 0개일 때까지 반복하여 출력한다.

⏱ 시간 복잡도

나올 수 있는 수가 K개라고 가정하면 N개의 수를 입력받으며 배열에 개수를 추가하고, 출력하기 위해 총 K개의 배열을 확인해야 하기 때문에 총 시간 복잡도는 O(N+K)가 된다.
따라서 수의 범위 K가 작을 때에는 Counting Sort가 효율적으로 동작한다.

 

 

📃 정리

• Counting Sort의 시간 복잡도는 O(N+K)다.
• K가 1000만 이하일 때 사용하면 효율적이다.