[CS] 계수 정렬(Counting Sort)

계수 정렬(counting sort) 알고리즘의 개념

• 계수정렬은 숫자들간 비교를 하지 않고 정렬을 하는 알고리즘
• 일일이 비교를 하지 않고 각 숫자가 몇개인지 센 다음에 정렬함
• 배열내 최대 값+1 만큼의 길이만큼의 메모리가 필요함
• 시간복잡도는 O(n)

과정 설명

1. 입력 배열의 원소들의 최대 값을 산출한다.

2. 최대값을 통하여 카운팅 배열을 만든다.

3. 카운팅 배열을 입력 배열의 원소의 갯수를 구한다.

4. 카운팅 배열의 누적합을 구한다.

5. 누적 합(카운팅 배열)통해 정렬하기 위한 입력 배열의 인덱싱을 구하여 새롭게 정렬할 배열에 저장한다.

6. 입력 배열이 접근한 누적합의 카운팅 개수를 뺀다.

계수 정렬(counting sort) C++ 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void counting_sort(vector<int>& v) {
	int max_v = *max_element(v.begin(), v.end()); // 입력 배열의 원소들의 최대 값을 산출한다. 
	vector<int> count(max_v+1,0);// 최대값을 통하여 카운팅 배열을 만든다.
	for (int i = 0; i < v.size(); i++) { 
		count[v[i]]++; //카운팅 배열을 입력 배열의 원소의 갯수를 구한다.
	}
	for (int i = 1; i < count.size(); i++) { 
		count[i] =  count[i]+count[i - 1] ; //카운팅 배열의 누적합을 구한다.
	}
	vector<int> sorted_v(v.size(),0);
	for (int i =0; i< sorted_v.size(); ++i) {
		sorted_v[count[v[i]]-1] = v[i]; //누적 합(카운팅 배열)통해 정렬하기 위한 입력 배열의 인덱싱을 구하여 새롭게 정렬할 배열에 저장한다. 
		count[v[i]]--; // 입력 배열이 접근한 누적합(카운팅 배열)의 카운팅 개수를 뺀다.
	}
	v = sorted_v;
}
int main()
{
	vector<int> v = { 10,412,345,100,23,149,23 };
	counting_sort(v);
	for (auto& e : v) {
		cout << e << endl;
	}
	return 0;
}