Counting Sort ( 계수 정렬 )
- Algorithm
- 2020년 10월 13일
계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm 이다.
그러면 여기서 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데, 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 된다.
1. 기본적인 흐름
2 1 2 4 5 3 6 5 3 을 정렬하고자 한다면
1의 개수는 1개, 2의 개수는 2개, 3의 개수는 2개, 4의 개수는 1개, 5의 개수는 2개, 6의 개수는 1개 이기 때문에 작은 수 부터 개수만큼 차례대로 나열하게 되면
1 2 2 3 3 4 5 5 6 으로 정렬이 된다.
2. 정렬 과정
- 정렬할 배열 A, 추가 배열 C를 생성
- 배열 C는 모든 값을 0으로 초기화
- 배열 A의 값을 토대로 배열 C의 인덱스값을 참조하여 값을 1씩 증가 (예를 들어 배열 A의 값중 3이 있다고 한다면, C의 3번째 인덱스 값을 1더해준다.)
- 배열 c의 각 값들을 직전 값을 더해 업데이트
(예를 들어, 배열 C가 1,0,2,2 였다면, 1,1,3,5로 업데이트) - 배열 C는 배열 A의 값들의 인덱스 값이므로, 배열 A를 끝에서부터 역순으로 훑으면서 배열 B에 정렬. (이때, 한 값을 B에 옮겨주었다면, 해당하는 인덱스의 배열 C의 값은 1을 빼준다.)
Note
여기서 배열 A의 뒤의 값부터 역순으로 훑으면서 정렬하는 이유는 counting sort 는 stable한 특성을 갖고있는 정렬인데, 앞에서부터 정렬을 하게 되면 stable한 특성이 깨지기 때문이다.
예를들어, 아래와 같은 배열 A가 있다면 원래 방법대로 뒤에서부터 훑게 되면 아래와 같이 정렬이 된다.
A = { 3 5(a) 1 4 5(b) 2 }
C = { 1 2 3 4 6 } 이 되어,
A = { 1 2 3 4 5(a) 5(b) }
반대로 똑같은 A를 앞에서 부터 훑게 되면 아래와 같이 나오게 되면서 stable한 특성이 깨지게 된다.
1 2 3 4 5(b) 5(a)
따라서 뒤에서 부터 훑으며 정렬을 하게 된다.
3. c++ 구현 코드
#include <iostream>
#include <cstdlib> //time
#include <ctime> //rand, srand
#include <string.h> //memset
#include <time.h> //시간 측정
using namespace std;
#define MAX_ARRAY_SIZE 64 //정렬할 배열 숫자 개수
int maxValue=0; //가장 큰 값
clock_t start, finish, used_time=0; //실행 시간 측정을 위한 변수
//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
srand((unsigned int)time(NULL));
for(int i=0;i<arrlen;i++){
array[i]=rand()%MAX_ARRAY_SIZE + 1;
maxValue = (maxValue < array[i]) ? array[i] : maxValue; //가장 큰 값 찾기
}
}
void display(int *array,int arrlen){
for(int i=0; i<arrlen;i++){
cout.width(3);
cout << i+1 <<". ";
cout.width(2);
cout << array[i] << endl;
}
}
//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
used_time=finish-start;
printf("\n*********** result **********\n time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}
int* count_sort(int *array,int arrlen){
int *c = new int[maxValue+1];
int c_size = maxValue+1;
int *b = new int[arrlen];
memset(c,0,c_size*sizeof(int)); //배열c 0으로 초기화
/*각 숫자 횟수 카운틱하며 c배열 인덱스 값 증가*/
for(int i = 0; i < arrlen ; i++){
c[array[i]]++;
}
/*배열 c의 인덱스 값 누적합 구하기*/
for(int i=1; i < c_size; i++){
c[i] += c[i-1];
}
/*배열 A역순으로 훑으며, 배열 C참조하여 정렬*/
for(int i = arrlen-1; i >= 0; i-- ){
b[c[array[i]]-1] = array[i];
--c[array[i]];
}
return b;
}
int main(){
int *array = new int[MAX_ARRAY_SIZE];
input_random(array,MAX_ARRAY_SIZE); //배열에 랜덤값 삽입
delete array;
start = clock();
array = count_sort(array,MAX_ARRAY_SIZE); //계수 정렬
finish = clock();
display(array,MAX_ARRAY_SIZE); //show array
CalcTime();
delete array;
return 0;
}
4. 특징
시간 복잡도는 O(n+k) 로 O(n) 또는 O(k) 를 갖는다.
( 여기서 n은 input의 개수, k는 input으로 들어온 n의 범위 == 추가 배열 c의 범위 )
Note
예를 들어 1,1,1,1,1,1,1,1 과같이 1이 10개로 n이 10이 들어왔다면, 이때 k는 2가 되고,
1 500 의 input이 주어진다면 n은 2에 불과하지만, k는 501이 된다.
범위가 넓어지게 되면 추가 메모리 공간이 많이 필요해지고, 또 범위를 계산해서 가장 큰 수가 무엇인지 판별하는 추가 로직도 도는 등 추가 작업이 필요하다.
따라서, 점수나 알파벳같은 좁은 범위의 데이터를 정렬할 때 유용하다.
stable 한 정렬 방법으로 radix sort 시 사용되는 정렬이다.
