[TIL-14 / 230702] 알고리즘 - 카운팅 정렬(Counting Sort)

알고리즘을 공부하면서 많은 정렬들이 등장한다. 버블 정렬, 삽입 정렬 등등...

오늘 공부한 내용은 이렇게 수많은 정렬 알고리즘 중 시간 복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다.

 

카운팅 정렬을 공부하면서 처음에는 이게 왜 빠를까?를 생각했다. 시간 복잡도를 공부할 때, 시간 복잡도 도출 기준은 상수의 시간 복잡도는 계산에서 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다고 배웠다.

 

카운팅 정렬은 각 배열 원소끼리(예를 들어 for문 중첩) 직접 비교하지 않고, 인덱스를 가지고 위치를 찾아나가는 것이다. 이 방법의 가장 큰 장점은 매우 빠르다는 것이다. 하지만 카운팅 정렬은 수의 범위가 매우 클 경우(예를 들어 10억, 100억 등등...) 심한 메모리 낭비를 하게 되기에 해당되는 상황에서만 사용한다.

 

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();
	}
 
}

결과값

카운팅 정렬을 공부하면서 처음에 왜 이렇게 정렬을 하지? 라는 고민을 했다.

알고리즘 문제들을 풀고 시간 초과 때문에 틀린 경험이 엄청 많았다.

 

많은 경우에, 미리 배열을 선언해두지 않고 입력받은 값에 맞는 배열의 크기를 선언하고 반복문을 돌리는...

그런 과정들 때문에 시간초과가 발생했었다.

 

이렇게 수의 크기가 적정 범위 내로 정해져 있다면, 카운팅 정렬을 사용하여 O(n)의 시간 복잡도 내로 정렬을 수행한다면, 보다 빠른 시간 내에 알고리즘 문제를 해결할 수 있을 것 같다. 앞으로 알고리즘 공부를 하면서 활용하려 노력해볼 계획이다.