카운팅 정렬
: non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추는 알고리즘
카운팅 정렬의 과정
input array = [2, 0, 1, 4, 5, 4, 3, 2, 0, 1, 1, 0, 5, 4, 3] 가 있을 때,
- 전체 원소 값의 빈도 수를 체크하여 counting array에 저장한다.
counting array = [3, 3, 2, 2, 3, 2]
예를 들어, counting array[0] = 3 은 인덱스 값이 0이 input array에 3개 존재함을 나타냄
- 카운팅 어레이의 각 요솟값에 직전 요솟값을 더해서 업데이트 해준다.
counting array = [3, 6, 8, 10, 13, 15]
예를 들어,
counting array[0] = 3 : 0은 output array[0]에서 output array[2]까지 3자리 차지한다.
counting array[1] = 6 : 1은 output array[3]에서 output array[5]까지 3자리 차지한다.
- 결과를 출력할 output array를 input array와 같은 길이로 생성한다.
output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
- 역순으로 input array의 요솟값을 output array에 채워 넣는다.
input array의 마지막 원소는 3이다. counting array[3] = 10을 참조하면 3은 output array[9]의 자리를 차지한다는 것을 알 수 있다.
(끝자리부터 채워 나간다.)
output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1]
한자리 채워 넣었으므로 counting array[3]의 값을 -1 한다. -> counting array[3] = 9
그다음 input array의 원소는 4이다.
counting array[4] = 13을 참조하면 4는 output array[12]의 자리를 차지한다는 것을 알 수 있다.
output array = [-1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, 4, -1, -1]
한자리 채워 넣었으므로 counting array[4]의 값을 -1 한다. -> 12
이렇게 채워나가는 작업을 반복하다 보면
output array = [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]처럼 정렬된 array를 얻을 수 있다.
