Counting Sort

• 특정 범위 내에서 각 요소의 발생 횟수를 카운트한 다음, 이 카운트 정보를 사용하여 정렬할 배열 내의 요소의 위치를 결정하는 선형 정렬 알고리즘
• 최대 값과 최소 값의 차이에 선형적이므로 , 범위가 크면 효율적이지 않을 수 있다.
• 큌 정렬(Quick Sort), 합병 정렬(Merge Sort)의 평균 시간복잡도는 O(nLogn)인데, 이에 반해 counting sort는 O(n)으로 속도가 빠른 알고리즘이다.

과정

1. 정렬할 배열과 최대값을 정의한다.

2. 최대값과 동일한 길이의 counting array를 생성한다.

3. 정렬할 배열의 각 원소값을 count한다.
   (원소값이 counting array의 인덱스가 되고, 해당 인덱스의 값을 ++ 해준다.)

4. counting array의 각 원소마다 누적 합계를 다시 계산한다.
   ex) countingArray[i] += countingArray[i -1];

5. 카운트 배열에서 원래 배열의 각 요소 인덱스를 찾는다.
   각 인덱스의 누적 카운트를 새로 정렬할 인덱스에 각 요소를 배치한다.

코드

// array = 정렬할 배열
// maxValue = 최대값
public static int[] countingSort(int[] array, int maxValue) {
	int[] countArray = new int[maxValue + 1];       // 카운트 저장할 배열
	int[] sortedArray = new int[array.length];      // 정렬된 배열

	// 정렬할 배열의 각 원소값을 count 한다.
	for(int value : array) {
		countArray[value]++;
	}	

	// 카운트된 값들의 누적합을 다시 계산해준다.
	for(int i=1; i < countArray.length; i++) {
		countArray[i] += countArray[i - 1];
	}

	// 정렬할 배열의 해당 원소의 카운트된 값을 sortedArray의 인덱스에 넣어준다.
	for(int i=array.length - 1; i >= 0; i--) {
		sortedArray[--countArray[array[i]]] = array[i];
	}

	return sortedArray;
}

백준 관련 문제
https://velog.io/@dayoung_sarah/백준-2751번-수-정렬하기2Java

[참고]
https://www.programiz.com/dsa/counting-sort