[알고리즘] 계수정렬

 

계수정렬 개념

---

정수형 데이터를 정렬하는 알고리즘 중 하나로, 데이터의 값을 기준으로 각 값의 등장 횟수를 세는 방법을 이용합니다.

 

먼저, 데이터를 순회하며 최소값과 최대값을 구합니다. 그 다음, 최소값부터 최대값까지의 범위를 가지는 카운트 배열을 만들어서 각 값이 몇 번 등장하는지 세어 저장합니다. 이를 통해 각 값이 몇 번 등장하는지를 누적해서 계산할 수 있게 됩니다.

 

그 다음, 카운트 배열을 순회하며 각 값이 몇 번 등장하는지 누적합을 계산합니다. 이를 통해 정렬된 결과를 저장할 배열의 인덱스를 결정할 수 있습니다. 마지막으로, 원래 배열을 역순으로 순회하며 각 원소를 정렬된 배열의 올바른 위치에 저장하면 정렬이 완료됩니다.

 

계수정렬의 시간 복잡도는 O(n+k)이며, n은 데이터의 개수이고 k는 데이터 중 최대값과 최소값의 차이입니다. 계수정렬은 데이터의 분포가 균등할 때 가장 빠른 정렬 알고리즘 중 하나이지만, 데이터의 분포가 치우쳐져 있거나 범위가 큰 경우에는 메모리 사용량이 크게 증가하여 비효율적일 수 있습니다.

 

 

계수정렬 코드

---

#include <stdio.h>
int main() {
	int n, num, visit[51]={0}, max=0;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &num);
		if(max<num) max=num;
		visit[num]++;
	}
	
	for(int i=0; i<=max; i++) {
		if(visit[i]!=0) {
			for(int j=0; j<visit[i]; j++) {
				printf("%d ", i);
			}
		}
	}
	
	return 0;
}

 

 

코드 설명

---

int n, num, visit[51], max=0;

 

n = 정수를 얼만큼 받을건지

num = 정수를 입력 받는 변수

visit[51] = 정수가 몇 번 입력 됐는지 기록할 배열

max = 받은 정수들 중 제일 큰 정수

 

 

scanf("%d", &n);
for(int i=0; i<n; i++) {
	scanf("%d", &num);
	if(max<num) max=num;
	visit[num]++;
}

 

n을 입력 받은 후 반복문을 통해 0부터 n-1까지 반복

반복해서 num을 입력 받는데 만약 입력 받은 num이 max 보다 크다면 max에 num 넣기

(정수가 몇번 입력 되었는지 알기 위해) visit 배열의 num 자리에 1씩 증가 시키기

 

 

for(int i=0; i<=max; i++) {
	if(visit[i]!=0) {
		for(int j=0; j<visit[i]; j++) {
			printf("%d ", i);
		}
	}
}

 

0부터 (받은 정수들 중 가장 큰 num) max까지 반복

만약 visit 배열의 i번째 수가 0이 아니라면, 0이면 반복할 필요가 없음(정수를 입력 받지 않았다는 뜻)

배열의 i번째 수만큼 i를 출력하기