[알고리즘] 정렬 알고리즘 - 계수 정렬 Counting Sort

 

계수 정렬 (Counting Sort) 알고리즘 : 

계수 정렬 = 도수 정렬 = 카운팅 정렬

요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘

 

1. 배열 내 요소 값들의 개수를 저장하는 카운팅 배열을 만든다

2. 카운팅 배열의 요소에 직전 요소의 값을 더해준다.

 

카운팅 배열

3. 배열과 같은 크기의 출력 배열을 만들고 입력 배열의 역순으로 출력 배열에 요소들을 채워넣는다.

   3-1. 배열 a의 맨 뒷 요소 8을 꺼내 counting[8]을 확인

   3-2. 배열 b의 counting[8]-- 후 counting[8] 자리에 8을 저장

4. 배열 b를 배열 a로 복사한다

출력 배열 b 채워넣기 

 

 

메소드 countingSort() : 배열 a를 카운팅 정렬

매개변수 : int[] a, int n

 

- 카운팅 정렬 : 

void countingSort(int[] a, int n) {
	int max = a[0];
	for(int i = 0; i < n; i++) {
		if(a[i] > max)
			max = a[i];
	}
	
	int[] counting = new int[max+1];
	int[] b = new int[n];
	
	for(int i = 0; i < n; i++) counting[a[i]]++;
	for(int i = 1; i <= max; i++) counting[i] += counting[i-1];
	for(int i = n-1; i >= 0; i--) b[--counting[a[i]]] = a[i];
	for(int i = 0; i < n; i++) a[i] = b[i];
}

 

 

 

 

카운팅 정렬 Counting Sort :

최선 = O(N), 평균 = O(N), 최악 = O(N)

안정한 정렬