Counting Sort
- 원소 간 비교 과정을 거치지 않고 정렬하는 방법
- 시간복잡도 = O(n)
- O(nlogn)의 Quick Sort(퀵 정렬)보다 빠르지만, 사용할 수 있는 경우가 제한적이다.
: 배열을 이용해 정렬을 수행하기 때문에 - 불필요한 메모리를 많이 잡아먹는다.
- 배열 인덱스를 기반으로 정렬을 수행하기 때문에, 음수/소수 일 경우에는 특정 값을 더하거나 곱해서 사용한다.
예시 - {5, 2, 3, 1, 4, 2, 3, 5, 1, 7} 을 카운팅 정렬 해보자.
1. input[] 배열의 최댓값 만큼의 countint[] 배열을 생성한다.
2. input[] 배열을 하나씩 읽어가며, 숫자가 나온 횟수를 카운팅하여 counting[] 배열에 저장한다.
3. counting[i] += counting[i-1] 과정을 통해 counting[] 배열 내에 값들을 누적시켜 수정한다.
4. 카운팅 정렬을 한다.
1) input[] 배열의 맨 마지막부터(input.length-1부터) 하나씩 탐색한다.
2) int temp = input[i] 라고 temp값을 저장한다면 - counting[temp]를 -1 해준다.
1),2) 과정을 위의 그림으로 설명하면
input[] 배열의 맨 마지막부터 정렬할 것이므로, input[input.length-1]인 숫자 7부터 정렬을 시작한다.
정렬을 할 것이므로 - 횟수를 저장한 정보는 필요가 없다.
그러므로 숫자 7의 횟수를 카운트했던 counting[]배열의 7번째 원소를 -1 해준다.
3) 1),2) 과정을 거치면 counting[] 배열은 '해당 인덱스의 숫자의 정렬 위치'를 의미한다.
위의 그림으로 설명을 이어서하면
counting[7]=9가 되고, 숫자 7은 result[9]의 위치에서 정렬이 완료된다.
카운팅 정렬 후의 counting[] 배열과 정렬된 결과인 result[] 배열은 다음과 같다.
예시처럼 같은 숫자가 중복되어있는 배열을 정렬하게 되면
counting[] 배열은 '해당 인덱스의 숫자의 정렬 위치'가 아니라, "해당 인덱스의 숫자가 정렬되어 시작되는 위치" 를 의미한다.
코드 구현
/*
input[] : 정렬 전 배열
counting[] : 숫자 횟수 카운트 및 카운팅 정렬에 사용되는 배열
result[] : 정렬 후 배열
inputMax : input[]의 최댓값
1.중복되는 숫자를 카운트한다. - counting[]에 저장
2.counting[]을 누적합 계산한다.
3.input[input.length-1]부터 해당 counting[]값을 -1하고,
result[]배열의 정렬된 위치에 값을 저장한다.
*/
public int[] countingSort(int[] input, int inputMax){
int[] counting = new int[inputMax+1];
int[] result = new int[input.length];
for(int i=0; i<input.length; i++){
counting[input[i]]++;
}
for(int i=1; i<counting.length; i++){
counting[i] += counting[i-1];
}
for(int i= input.length-1; i>=0; i--){
result[--counting[input[i]]] = input[i];
}
return result;
}