[Algorithm] 계수정렬(Counting Sort)

백준 문제를 푸는데 Arrays.sort를 활용해 정렬을 했더니 시관 초과가 났다.

 

Arrays.sort는 dual pivot QuickSort 알고리즘을 사용해 평균 시간복잡도가 O(nlong)인 매우 빠른 알고리즘에 속한다고 한다. 하지만 최악의 경우 O(n^2) 이 될 수도 있다는데..

 

해당 백준 문제에서는 Arrays.sort()를 쓰지 못하게 O(n^2)이 걸리도록 저격한 데이터가 있었고...

 

여기서 알게된 계수정렬(Counting Sort)을 정리해보고자 한다.

 

 

 

계수정렬(Counting Sort) 가 뭔데?

 

계수정렬은 수많은 알고리즘 중 시간복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다.

대표적인 빠른 정렬 알고리즘으로 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort) 등이 있는데, 이들의 평균 시간 복잡도는 O(nlogn)인 것에 비한다면 엄청난 속도이다.

 

기본적으로 정렬은 데이터끼리의 비교가 대부분이어서 O(nlogn)보다 작아질 수 없다.

 

그렇다면 계수정렬은?

계수정렬의 메커니즘은 데이터끼리의 비교없이 데이터의 값이 몇 번 나왔는지 세주는게 끝이다.

 

 

 

아래와 같은 배열이 있다고 가정해보면

 

과정 1

array를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index로 하는 새로운 배열(counting)의 값을 1 증가시킨다.

array[0]의 value가 7이므로 Counting배열의 index 7 의 값을 1 증가시킨다 말그대로 각 값의 갯수를 세주는 배열이다

 

과정 2

 

counting 배열의 각 값을 누적합으로 변환시킨다.

 

 

이렇게 누적합을 구한다면 아래와 같은 두개의 배열 형태를 갖게 된다.

 

 

과정 3

 

위에서 나온 counting 배열의 각 값은 (시작점 - 1)을 알려준다. -> 난 이 부분이 아무리 봐도 이해가 가지 않아서 한참을 생각했다....

앞서 봤듯이 array의 index가 counting의 value가 되고 value가 counting의 index가 되었으니 다시 counting의 index가 결과값의 value로 value - 1 이 index로 간다는 것 즉 순서대로 정렬 된다는 것이다.

 

안정적으로 정렬하기 위해서는 array의 마지막 index부터 순회하는 것이 좋다고 한다.

 

이렇게 하면 result는 정렬된 배열의 값이 나오게 된다..!

이 과정에서 데이터끼리의 비교는 없기 때문에 빠른 배치가 가능하지만 단점 또한 존재한다.

counting이라는 배열을 선언해줘야 한다는 것

만일 10개의 원소를 정렬하고자 하는데, 수의 범위가 0~1억이라면 메모리 낭비가 매우 심할 것이다.

 

즉! Counting Sort가 효율적인 상황에서 쓰이려면 수열의 길이보다 수의 범위가 극단적으로 크면 안된다는 것이다.

 

아래는 알고리즘을 구현한 코드이다.

머리로는 이해를 했지만 알고리즘을 활용하려면 더 공부가 필요할 것 같다...

public class CountingSort {
	public static void main(String[] args) {
		
		int[] array = new int[100];		// 수열의 원소 : 100개
		int[] counting = new int[31];	// 수의 범위 : 0 ~ 30
		int[] result = new int[100];	// 정렬 될 배열 
		
		for(int i = 0; i < array.length; i++) {
			array[i] = (int)(Math.random()*31);	// 0 ~ 30
		}
 
		
		// Counting Sort
		// 과정 1 
		for(int i = 0; i < array.length; i++) {
			// array 의 value 값을 index 로 하는 counting 배열 값 1 증가 
			counting[array[i]]++;			
		}
		
		// 과정 2 
		for(int i = 1; i < counting.length; i++) {
			// 누적 합 해주기 
			counting[i] += counting[i - 1];
		}
		
		// 과정 3
		for(int i = array.length - 1; i >= 0; i--) {
			/*
			 *  i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤 
			 *  counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
			 */
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;
		}
		
		
		
		/* 비교 출력 */
		
		// 초기 배열 
		System.out.println("array[]");
		for(int i = 0; i < array.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(array[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// Counting 배열 
		System.out.println("counting[]");
		for(int i = 0; i < counting.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(counting[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// 정렬된 배열
		System.out.println("result[]");
		for(int i = 0; i < result.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(result[i] + "\t");
		}
		System.out.println();
	}
 
}

 

 

References

https://st-lab.tistory.com/104?category=856997