| 계수정렬 | 기수정렬 | 버킷정렬 |

■ 분포에 의한 정렬

• 지금까지 살펴본 알고리즘은 모두 입력 원소의 값을 비교하여 정렬 순서를 결정하는 비교 기반
  정렬 알고리즘임
• 비교 기반 정렬 알고리즘은 최악의 경우 비교 횟수가 O(nlogn)임
• 키를 비교하는 것이 아니라 키의 분포를 이용함으로써 계산 시간을 O(n)으로 줄일 수 있음
• 여기에서 제시되는 계수 정렬, 기수 정렬, 버킷 정렬은 최악 또는 평균 실행시간이 O(n)임

■ 계수 정렬

• 계수 정렬(counting sort)은 입력 키가 어떤 범위, 예를 들어 1부터 k사이의 작은 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법
• 어떤 입력키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있음
  예를 들어 입력 키들이 숫자일 때 입력에 10이라는 키가 있고 이 보다 작은 키가 5개 있다면 10은 정렬 순서에서 6번째에 위치할 것임
• 계수 정렬에서는 입력 키들이 범위 k 내의 각 값에 대하여 입력 키가 실제로 입력에 나타나는 횟수를 계산