[10989.java] Counting Sort()

Counting Sort() 카운팅정렬

• 시간복잡도가 𝚶(𝑛) 으로 속도가 빠른 알고리즘
• 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort) 의 평균 시간복잡도는 𝚶(nlogn) 인데 카운팅 정렬은 시간복잡도가 𝚶(𝑛) 으로 속도가 아주 우수한 알고리즘
• 각 값의 개수가 담겨있는 배열

1. 배열을 쭉 돌면서 해당 값을 index로 하는 새로운 배열의 값을 1 증가
   array[0] = 7 이므로 counting[7] 값을 1 증가,
   array[1] = 2 이므로 counting[2] 값을 1 증가,
   ...
   array[11] = 1 이므로 count[1] 값을 1 증가.
   

2. 완성된 counting 배열의 각 값을 누적합으로 변환
   

counting[1] -> counting[0] + counting[1]
counting[2] -> counting[1] + counting[2]
...
counting[7] -> counting[6] + counting[7]

우리는 지금 위와 같은 두 배열을 갖고 있는 중.

누적합 왜? 시작점 구하기 위해서
counting 배열의 각 값은 (시작점 - 1)

3. 최종적으로 정렬
   counting 배열의 각 값은 (시작점 - 1)
   -> 즉, 해당 값에 대응되는 위치에 배정

array[11] = 1, counting[1] = 3
-> (counting[1] -1)의 값 (2)이 새로운 배열의 인덱스 result[2]=array[11] = 1에 위치

• array의 마지막 인덱스 값부터 진행

왜 빠르냐? 두 수를 비교하는 과정이 없기 때문에!
그러나, 10개의 원소를 정렬할건데 수의 범위가 1억이라면 이건 메모리 낭비

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

참고1
참고2