[알고리즘 정리] Counting Sort ( 계수 정렬 ) - O(N+k), 추가 메모리, Stable

Counting Sort (계수 정렬) 이란?

계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다.

 

백준 문제

https://www.acmicpc.net/problem/2751

 

 

과정

과정은 간단하다.

 

1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기

2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기

3. 각 값의 개수를 누적으로 바꾸기

4. 뒤에서부터 자리 찾아주기

 

위 순서에 따라서 위 arr 배열을 정렬해보자

1. 가장 큰 값을 찾는다.  ➡️ max = 5

2. 각 값의 개수를 담는다. 

arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다.

 

 

3. 각 값의 개수를 누적으로 바꾸기

누적으로 바꾼다는 것은 앞서 나온 개수들을 자기까지 모두 더한다는 것이다.

count[i] = count[i] + count[i+1]

 

이때 이 누적값을 통해서 값 2는 2번째 ~ 3번째 위치에 존재한다는 것을 알아낼 수 있다.

값 5는 6번째 ~ 7번째 위치에 존재한다는 것을 나타낸다.

 

4. 뒤에서부터 자리 찾아주기

 

 

 

 

 

 

 

 

 

 

 

하면 정렬 끝!

 

 

특징

1. 시간복잡도 : 원소의 개수를 N, 가장 큰 값을 K라고 할때, 최선 O(N + K) , 최악 O(N+K)   

정렬 중에서 빠른 편이다. Counting sort를 효율적으로 쓸 수 있는 경우는 O(N +K) ~ O(N)일때 즉, 원소의 개수가 가장 큰 원소의 값이랑 비슷할때 이다.

2. Stable 한 정렬

구현 시 누적합 배열에 따라서 원소를 알맞은 자리에 넣는 과정에서 원소 순회를 뒤쪽부터 하기 때문에 stable한 정렬이 된다.

3. 개수를 세고 누적합을 만들기 위해서 K만큼의 배열을 만들어 추가 메모리가 필요하다(단점)

구현 시 누적합 배열에 따라서 원소를 알맞은 자리에 넣는 과정에서 원소 순회를 뒤쪽부터 하기 때문에 stable한 정렬이 된다.

💡stable한 정렬

수 x, z, x' y, x'' 를 정렬하려고 할때 x 들은 모두 같은 수라고 가정하다.

이를 정렬하면 x, x' ,x'', y, z 로 정렬되게 되는데 x의 순서가 바뀌지 않고 그대로 정렬되는 것을 stable한 정렬이라고 한다.

 

 

코드

public class CountingSort {
	public static void main(String[] args)  {
		int arr[] = new int[] {4,5,5,2,1,3,2};
		
		
		// 1. 가장 큰 값 찾기
		int max=0;
		for (int i = 0; i < arr.length; i++) {
			max = max < arr[i] ? arr[i] : max;
		}
		


		//2. 각 값의 갯수 담기
		int count[] = new int[max+1];
		for (int i = 0; i < arr.length; i++) {
			count[arr[i]]++;
		}
        
		
		//3. 누적으로 바꾸기
		for (int i = 1; i<count.length; i++) {
			count[i]+=count[i-1];
		}
        
        
		
		//4. 자리 찾아주기
		int result[] = new int[arr.length];
		for (int i = arr.length-1; i >= 0; i--) { //뒤에서부터 탐색
			int n = arr[i];
			result[count[n]-1] = n;
			count[n]--;
		}
		
        
        
	}
}

 

 

실행 결과

위 과정을 보기좋게 찍어보면 아래와 같다.