[C++][구현] 계수 정렬 (Counting Sort)

⭐ 주제

 

만약 숫자를 정렬하고 싶다고 했을 때, 그 숫자의 범위를 알고 있다면, counting 을 하여 정렬을 할 수 있습니다.

 

숫자의 범위가 0이상의 정수인 k까지 일 때,

정렬하고 싶은 arr를 돌면서 숫자가 몇번 출현 했는지를 보고 

그 수의 인덱스의 count를 1씩 올려줍니다.

 

인덱스가 올라갔으면 인덱스를 가지고 0부터 k까지 count를 더해주어 각 숫자에 대한 인덱스를 알 수 있께 해줍니다.

 

이 후 정렬을 해야할 배열의 끝부터 0까지 인덱스를 찾아가면서 정렬을 해주면 됩니다.

---

 

#include <iostream>
using namespace std;
// O(n + k)

void countingSort(int nums[], int length, int size) {
	int* SortedArr = new int[length];
	int* count = new int[size] {0,};
	int* acc_count = new int[size] {0,};

	for (int i = 0; i < length; i++) {
		count[nums[i]]++;
	}

	int tmp(0);
	for (int i = 0; i < size; i++) {
		tmp += count[i];
		acc_count[i] = tmp;
		acc_count[i]--; // count 라는 개수에서 인덱스로 바꿔주기 위해서.
	}

	// stable 하게 하기 위해서 역순으로 해줍니다.
	for (int i = length - 1; i >= 0; i--) {
		int idx = acc_count[nums[i]]--;
		SortedArr[idx] = nums[i];
	}

	// 정리된 arr를 옮겨줍니다.
	for (int i = 0; i < length; i++) {
		nums[i] = SortedArr[i];
	}
	
	delete[] count;
	delete[] acc_count;
	delete[] SortedArr;
}


int main() {
	int nums[7] = { 3, 4, 0, 1, 2, 5, 0 };
	countingSort(nums, 7, 6);

	for (int i = 0; i < 7; i++) {
		cout << nums[i] << ' ';
	}
}

 

시간 복잡도는 O(n + k) 이고, 역순으로 찾아가면 stable하게 만들 수 있습니다.