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

■ 버킷 정렬의 개념

• 앞에서 설명한 계수 정렬을 버킷 정렬(bucket sort)로 부르는 경우도 있으나 여기서의 버킷 정렬은 계수 정렬을 일반화한 것으로 간주할 수 있음
• 계수 정렬은 키 값이 작은 범위 안에 들어올 때 적용 할 수 있는 방법이지만 버킷 정렬은 키 값의 범위뿐만이 아니라 그 범위 내에서 키 값이 확률적으로 균등하게 분포된다고 가정할  수 있을 때 적용할 수 있는 방법
• 설명의 편의상 키 값이 0과 1 사이라고 가정하자. n개의 키가 구간[0,1]을 n등분하고 이들 각각을 하나의 버킷으로 한다. 각 키를 크기에 따라 각 버킷에 분배한다면, 키가 구간내에서 균등하게 분포한다고 가정했으므로 하나의 버킷에는 하나의 키만 들어있을 확률이 높음
• 만약 한 버킷에 여러 키가 들어가게 된다면 같은 버킷에 속하는 키끼리는 간단한 정렬 알고리즘으로 정렬함
• 이러한 버킷에 대하여 버킷 순서에 따라 데이터를 출력하면 정렬된 결과를 얻을 수 있음