Counting Sort(카운팅 정렬) : 계수 정렬

카운팅 정렬의 개념

기존 정렬처럼 데이터 자체를 메모리에 저장하여 정렬하는 것이 아니라, 

데이터의 개수를 세주는 방식을 통한 정렬.

데이터를 직접 저장하지 않기 때문에, 

메모리 상으로도 굉장히 효율적이고 시간 복잡도도 굉장히 작다.

 

시간 복잡도

O(n)

빠르다고 알려져있는 다른 정렬들(대표적으로 Quick Sort, Heap Sort, Merge Sort 등)의 시간 복잡도가

O(nlogn) 인 걸 생각했을 때, 굉장히 빠른 속도이다!

 

구현 방법

DAT(Direct Adress Table, 해시 테이블)을 이용한다.

Counting 값을 기록하는 용도의 배열을 만들고 0으로 배열 전체를 초기화 해둔다.

 

이후, 

1이 나왔다면 arr[1] += 1;

3이 나왔다면 arr[3] += 1;

8이 나왔다면 arr[8] += 1;

...

 

이런식으로 숫자값을 index로 한 후, 값이 나올때마다 카운팅을 더해주면 된다. 

 

이후 

누적합으로 배열을 만들어주는 부분, 

뒤에서부터 값을 채워주는 부분은 이해가 안됨