계수 정렬(Counting Sort)

개념 요약

• 벡터 내의 원소는 양수만 가능하며 값의 범위가 너무 크지 않아야 한다.
• 해당 벡터에 각 숫자가 몇 개가 나오는지 세서 차례대로 다시 저장한다.

 

---

정렬 과정

1. 주어진 벡터 내의 원소의 개수를 센다.
2. 차례대로 다시 벡터에 넣는다.

 

---

코드

void	counting_sort(std::vector<int> &unsorted_array)
{
	int	max_num = 0;
	// 원소중 최댓값을 뽑는다.
	for (auto &elem : unsorted_array)
		if (max_num < elem)
			max_num = elem;
	// 최댓값만큼의 공간을 가진 벡터 생성
	std::vector<int>	counting(max_num + 1, 0);
	// 원소의 해당하는 인덱스의 값을 증가
	for (auto &elem : unsorted_array)
		++counting[elem];
	// 원래 배열 초기화
	unsorted_array.clear();
	// 인덱스를 확인하면서 차례대로 원래 배열에 push
	for (int idx = 0; idx < max_num + 1; ++idx)
	{
		while ((counting[idx]--) != 0)
			unsorted_array.push_back(idx);
	}
}

---

시간 복잡도

• $O(n + k)$
  • k는 주어진 벡터 내 원소의 최댓값

---

공간 복잡도

• $O(k)$
  • k는 주어진 벡터 내 원소의 최댓값

---

장단점

• 시간 복잡도가 O(n)이다.
• 벡터 내의 원소의 최댓값만큼의 벡터를 생성해야 한다.