정렬9) 카운팅 정렬(Counting Sort)

* 카운팅 정렬
- 값의 갯수를 세고, 그 갯수에 따라 위치를 정해주는 방식(데이터간 크기 비교가 아니다)
- 비교 데이터가 작을 때 아주 빠르나, 데이터가 많으면 속도가 늦어진다.
- 추가 메모리를 요구한다.


* 정렬 원리
step0. 원본 배열


step1. 최대 데이터까지 데이터의 갯수를 모두 count 한다
    count[0] = 0;
    count[1] = 2;
    count[2] = 1;
    count[3] = 2;

step2. 카운트의 값을 누적합으로 변경 => 이 누적합은 해당 데이터의 최대 index 의미
    count[1] += count[0];    =>    count[1] = count[1] + count[0] = 2 + 0 = 2;
    count[2] += count[1];    =>    count[2] = count[2] + count[1] = 1 + 2 = 3;
    count[3] += count[2];    =>    count[3] = count[3] + count[2] = 2 + 3 = 5;

step3. 배열에 카운트를 -- 하여 정렬
    
    - count[3] = 5; 이므로 배열의 arr[count[3]--] 자리에 3을 넣으면 정렬 된다.

step4. 3과정 반복
    
    - count[2] = 3; 이므로 arr[2] 자리에 2를 넣고 정렬

step5. 3과정 반복
    
    - count[3] = 4; 가 되어 있으므로 arr[3] 자리에 3 넣고 정렬

step6. 마지막 인덱스 까지 위 과정 반복하면 정렬 완료



* 시간 복잡도
    - O(n)