[알고리즘] 계수정렬(counting sort)

오늘은 계수정렬에 대해 알아보겠습니다.

 

계수정렬은 x보다 작은 원소의 개수가 i-1개 라면, 정렬 후 x는 i번째에 위치해야 한다는 것을 이용합니다.

 

아래와 같은 arr배열에 있는 수를 정렬해야 한다고 할 때, arr 안에 있는 각 숫자가 몇 개 들어있는지 저장하는 cnt배열이 있습니다.

cnt배열의 크기는 (arr 안에 있는 숫자 중 가장 큰 수 - 가장 작은 수 + 1)로 지정할 수 있습니다.

cnt배열은 0으로 초기화 해준 뒤, arr 안에 있는 각 숫자가 몇 개 들어있는지 저장해야 합니다.

 

 

 

그 다음 cnt배열의 값들을 누적해서 다시 cnt에 저장하면 그것이 각 수가 저장될 배열의 위치가 됩니다. 이 부분에 맨 처음에 말한 "x보다 작은 원소의 개수가 i-1개 라면, 정렬 후 x는 i번째에 위치해야 한다." 는 것을 이용하는 부분입니다.

아래 누적cnt 배열을 보면 cnt 인덱스 5에 저장된 값은 8입니다. 즉, arr에 저장되있는 5라는 숫자는 8번째에 저장되어야 한다는 것입니다. 

 

정렬되는 모든 과정을 그림으로 표현해보겠습니다.

정렬된 것은 보라색, 현재 정렬할 것은 화살표로 표시하겠습니다. 

그리고, 같은 수가 여러개 있을 경우를 생각해서 정렬한 후 cnt의 값을 하나씩 줄여주어야 합니다.

 

 

 

 

 

 

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

void countingSort(int arr[], int sorted[], int n) {
	int min = arr[0], max = arr[0];
	for (int i = 1; i < 8; i++) {
		if (min > arr[i]) min = arr[i];
		if (max < arr[i]) max = arr[i];
	}

	//cnt 초기화
	int size = max - min + 1;
	int* cnt = (int*)malloc(sizeof(int) * size);
	for (int i = 0; i < size; i++) {
		cnt[i] = 0;
	}

	//cnt에 각 숫자의 개수 저장
	for (int i = 0; i < 8; i++) {
		cnt[arr[i]]++;
	}

	//cnt 누적합
	for (int i = 1; i < size; i++) {
		cnt[i] += cnt[i - 1];
	}

	//정렬하기
	for (int i = 7; i >= 0; i--) {
		sorted[cnt[arr[i]] - 1] = arr[i];
		cnt[arr[i]]--;
	}
	free(cnt);
}

int main() {
	int arr[8] = { 2,5,3,0,2,3,0,3 };
	int sorted[8];
	
	countingSort(arr, sorted, 8);
	for (int i = 0; i < 8; i++) {
		printf("%d\n", sorted[i]);
	}
	return 0;
}