(출처: Introduction to Algorithms)

 

계수 정렬(Counting sort, 카운팅 소트)에 대해 알아봅시다.

입력 원소들끼리 비교해 정렬을 하는 이른바 비교 정렬(Comparison sort)은 최악의 경우 비교를 \(\Omega(n\lg n)\)번 해야 합니다.

하지만 비교정렬이 아닌 정렬 방법은 \(\Omega(n\lg n)\)이라는 한계가 적용되지 않습니다.

계수 정렬은 선형 시간(O(n))에 수행됩니다.

 

 

계수 정렬 알고리즘

계수 정렬은 n개의 입력 원소가 [0, k] 범위에 있는 정수라고 가정합니다.

k=O(n)일 때 계수 정렬은 \(\Theta(n)\) 시간에 수행됩니다.

 

Fig 1. 계수 정렬의 pseudo-code (배열 범위에 주의)

알고리즘은 단순합니다.

  • 1. 정렬할 배열 A를 입력받고, 정렬된 배열이 담길 배열 B를 만든다
  • 2. [0, k(배열 내 최대값)]의 배열 C를 만들고 0으로 초기화한다
  • 3. 입력 배열을 순회하면서 원소의 값이 i라고 하면 C[i]의 값을 1 늘린다
    • 이 과정을 마치면 C[i]는 i의 개수를 나타낸다
  • 4. i=[1, k]까지 C[i] += C[i-1]을 수행한다
    • 이 과정을 마치면 C[i]는 i 이하 원소의 개수를 나타내게 된다
  • 5. 입력 배열을 순회하면서 원소 i에 대해 B[C[i]] = i, --C[i]; 를 수행한다
    • C 배열의 값이 원소의 위치가 됩니다. 같은 원소가 여러개 있는 경우의 인덱스를 계산하기 위해 C 배열의 값을 빼줍니다. 
    • 순회방향(앞->뒤, 뒤->앞)은 상관 없습니다

 

Fig 2. 카운팅 소트 진행과정

그림으로 보면 위와 같습니다.

보면 배열 원소끼리 비교하는 부분이 없다는 걸 알 수 있습니다.

 

 

장점과 단점 (Pros and Cons)

  • 장점
    • 선형 시간에 수행된다: \(\Theta(n)\)
    • 안정된 정렬(Stable sort)이다: 출력 배열에서 값이 같은 숫자가 입력 배열에 있던 것과 같은 순서로 나타납니다
  • 단점
    • 입력 범위에 비례한 카운팅 배열, 결과값 배열을 할당해야 한다 --> 메모리도 추가로 써야하고, 정렬할 값의 범위가 크면 비효율적

 

 

구현 (C++)

std::vector<int> counting_sort(std::vector<int>&& v) {
	auto k = *max_element(v.begin(), v.end());
	std::vector<int> count(k + 1);

	for (const auto& c : v)
		++count[c];

	for (int i = 1; i <= k; ++i)
		count[i] += count[i - 1];


	std::vector<int> ret(v.size());
	for (const auto& c : v) {
		ret[count[c] - 1] = c;
		--count[c];
	}

	return ret;
}

C++로 구현해본 코드입니다.

 

계수 정렬은 종종 기수 정렬(Radix sort)의 서브루틴으로 쓰이는데, 그 이유와 적용 방법은 기수 정렬 게시물에 올리겠습니다.

반응형

'알고리즘 > 정렬' 카테고리의 다른 글

기수 정렬 (Radix Sort (LSD))  (0) 2020.07.10