[삼성 알고리즘] 계수 정렬 (Counting Sort)

1. 계수 정렬(Counting Sort)

계수 정렬은 특정한 범위 내 숫자만 존재하는 경우에 극한의 효율을 발생시키는 정렬 알고리즘으로 빅오 표기법으로 O(N)의 성능을 뽑아낸다.

 

-> 여기서 특정한 범위 내 숫자란 0~5와 같이 좁은 범위를 말하며 0, 1, 2, 3, 3, 2, 1 ,4 와 같이 특정 범위 내 숫자들이 중복해서 있는 경우에도 효과적으로 나열할 수 있다.

 

 

  2. 동작 방식

위 계수 정렬 알고리즘의 동작 방식은 아래와 같이 여러 단계로 나누어져 있다.

예를들어 arr = { 4, 5, 6, 2, 2, 4, 1, 3, 5 } 와 같을 때

 

 

   1) 각 숫자의 개수를 파악 한다.

Index(숫자)	0	1	2	3	4	5	6
Value(개수)	0	1	2	1	2	2	1

 

   2) 위 파악한 숫자를 누적으로 계산 함.

Index(숫자)	0	1	2	3	4	5	6
Value(개수)	0	1	3	4	6	8	9

누적 값을 계산하는 이유는 마지막 과정에서 정렬을 진행할 때 자기 자리를 배열내 원소들이 각자 자신의 자리를 O(1)로 찾아가게 하기위한 전초 작업이다. 해당 작업이 필요한 이유는 3)에서 정렬을 진행할 때 확인할 수 있음.

 

 

   3) arr 인덱스 가장 뒤에 존재하는 값부터 거꾸로 2) 표를 통해 자리를 찾아 감.

가장 뒤에 존재하는 5의 경우 2) 표에서 8을 나타내므로 8번째 자리로 감(인덱스 0부터 시작) <정렬된 배열을 new_arr이라고 하자.>

즉 new_arr[7]=5가 된다. 즉 2)의 value는 해당 숫자의 자리 값을 의미하며 여기서 중요한 포인트는 자리 배치 후 2) 표의 해당 value값을 1 감소시켜야 하는 부분이다.

 

다시 정리하면 결과적으로 arr[8]의 값 5에 대해서는 정렬이 진행되면

2)의 표는

Index(숫자)	0	1	2	3	4	5	6
Value(개수)	0	1	3	4	6	7	9

이 되고 new_arr[7]=5가 된다.

 

마찬가지로 같은 방식을 arr[7]인 3에 적용하면

Index(숫자)	0	1	2	3	4	5	6
Value(개수)	0	1	3	3	6	7	9

가 되고 new_arr[3]=3이 된다.

 

과정을 반복해서 정렬을 진행하면 우리는 정렬된 배열 new_arr = {1, 2, 2, 3, 4, 4, 5, 5, 6}의 결과를 얻을 수 있다.

 

 

  3. 소스 코드

위와 같이 계수 정렬을 진행할 수 있으며 결과적으로 각 과정은 O(N)의 시간복잡도를 가지며 전체적인 시간 복잡도 역시 O(N)이 된다.

아래는 해당 계수 정렬을 간단하게 구현한 코드 입니다.

 

#include <iostream>

#include <algorithm>

 

using namespace std;

 

//Only positive numbers

int* counting_sort(int* arr, int size) {

int max = 0;

for (int i = 0; i < size; i++) {

if (max < arr[i])

max = arr[i];

}

 

//Initialize

int* buf = new int[max + 1];

for (int i = 0; i < max + 1; i++) {

buf[i] = 0;

}

 

//1st Counting numbers

for (int i = 0; i < size; i++) {

buf[arr[i]] += 1;

}

 

//Accumulate

for (int i = 1; i < max + 1; i++) {

buf[i] += buf[i - 1];

}

 

//Sort

int* new_arr = new int[size];

for (int i = size - 1; i >= 0; i--) {

new_arr[buf[arr[i]] - 1] = arr[i];

buf[arr[i]] -= 1;

}

return new_arr;

}

 

int main(void) {

int arr[5] = { 3,5,3,4,2 };

int size = 5;

int* answer=counting_sort(arr, size);

 

for (int i = 0; i < size; i++) {

cout << answer[i] << endl;

 

}

return 0;

}