개념 요약
- 벡터 내의 원소는 양수만 가능하며 값의 범위가 너무 크지 않아야 한다.
- 해당 벡터에 각 숫자가 몇 개가 나오는지 세서 차례대로 다시 저장한다.
정렬 과정
- 주어진 벡터 내의 원소의 개수를 센다.
- 차례대로 다시 벡터에 넣는다.
코드
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)이다.
- 벡터 내의 원소의 최댓값만큼의 벡터를 생성해야 한다.
'CS공부 > Algorithm' 카테고리의 다른 글
해시 테이블(Hash Table) (0) | 2022.06.23 |
---|---|
이분 탐색(Binary Search) (0) | 2022.06.22 |
기수 정렬(Radix Sort) (0) | 2022.06.22 |
힙 정렬(Heap Sort) (0) | 2022.06.21 |
병합 정렬(Merge Sort) (0) | 2022.06.21 |