정렬 - Counting Sort (계수 정렬)

1. 정렬되지 않은 숫자 배열이 있다.
   1. [0, 1, 2, 3, 2, 5, 0, 5, 2, 3]
2. 각 숫자의 개수를 센다.
   1. 0은 2개
   2. 1은 1개
   3. 2는 3개
   4. 3은 2개
   5. 4는 0개
   6. 5는 2개 
3. 이걸 배열로 만든다.(이걸 숫자 카운트 배열이라 하겠다)
   1. 이때 숫자는 인덱스로
   2. 개수는 값으로 한다.
   3. [2, 1, 3, 2, 0, 2]
4. 왼쪽에서 오른쪽으로 누적합을 계산한다. (이걸 누적합 배열이라 하겠다)
   1. [2, 3, 6, 8, 8, 10]
   2. 각각의 값들이 정렬될 배열의 인덱스를 알려준다. (아래에서 다시 설명한다.)
   3. 그런데 이상하다!
   4. 값들이 인덱스라고 했는데 마지막 값에 10이 있다.
   5. 나는 10개의 배열(인덱스 0~9)을 정렬하는데 인덱스 10이 나오다니?
   6. 그렇다.
   7. 여기서 전체 배열에 -1을 해줘도 되고
   8. 아니면
   9. 나중에 인덱스를 확인하고 값을 넣을 때 -1을 해줘도 된다.
   10. 본인은 누적합 배열에서 미리 -1을 하겠다.
   11. 따라서,
   12. 누적합 배열은 아래와 같이 완성된다.
   13. [1, 2, 5, 7, 7, 9]
5. 정렬
   1. 정렬할 배열 : [0, 1, 2, 3, 2, 5, 0, 5, 2, 3]
      1. 가장 뒤부터 왼쪽으로 오면서 정렬한다.
      2. 가장 뒤의 값이 3
   2. 누적합 배열에서 인덱스가 3인 값을 확인한다 -> 7
      1. [1, 2, 5, 7, 7, 9]
   3. 새로운 배열(정렬된 값을 넣을 배열)을 만들어 7번째 인덱스에 3을 넣어주고 7에 -1을 하여 6으로 변경한다. (다른 3이 들어갈 자리를 알려줌)
      1. 누적합 배열 : [1, 2, 5, 6, 7, 9]
      2. 정렬된 배열 : [null, null, null, null, null, null, null, 3, null, null]
   4. 이렇게 2번부터 4번까지 반복하면 된다.
   5. 한번 더
   6. 정렬할 배열 : [0, 1, 2, 3, 2, 5, 0, 5, 2, 3]
   7. 다음 정렬할 값 : 2
   8. 누적합 배열에서 인덱스가 2인 값 : 5
      1. [1, 2, 5, 6, 7, 9]
   9. 정렬된 값을 넣을 배열의 5번째 인덱스에 2를 넣어주고 5에서 -1 하여 4로 만든다.
      1. 누적합 배열 : [1, 2, 4, 6, 7, 9]
      2. 정렬된 배열 : [null, null, null, null, null, 2, null, 3, null, null]
   10. 2번부터 4번까지 반복.
6. 정렬 완료
   1. [0, 0, 1, 2, 2, 2, 3, 3, 5, 5]

---

참조 : bowbowbow.tistory.com/8

Counting Sort : 계수 정렬