[Algotithms] Bucket Sorting - 버켓 소팅 , distribution sort 의 일종

여러개의 bucket의 array 로 partitioning 해서 정렬 한다.

각각의 bucket 은 각각 서로 다른 sorting 알고리즘을 이용하여 정렬 할 수도 있고, bucket sorting 을 recursive 하고 사용하여 정렬 해도 된다.
pigeonhole sort 의 일반화된 게 bucket sorting 이다. ( pigeonhole sort 는 또 뭔가 )
숫자들을 비교해서 정렬하는게 아니므로 시간 복잡도를 O(n * Log(n)) 이라고 할수는 없다 

1. 빈 bucket list 를 만든다. 범위 구간은 필요한 만큼 알아서 적절히 나눈다.
2. 정렬할 list 를 한번 스캔 하면서 각각의 범위에 맞는 bucket 에 집어 넣는다.
3. 비어있지 않는 bucket 들만 각각 정렬 한다.
4. 제일 처음의 bucket 부터 차례로 append 하면 정렬 끝.  

bucket 을 2개로만 나누고 각각의 bucket 을 bucket sorting 을 이용해서 정렬 하는게 바로  quick sort 가 된다. 
bucket sorting 을 recursive 하게 사용하면 radix sort ! 와 유사 
참조. http://en.wikipedia.org/wiki/Bucket_sort


bucket 을 적절히 혹은 작은 단위로 쪼갰을 경우에는 각각의 bucket 을 insertion sort 로 정렬해도 매우 효율적이다. ( insertion sort 의 경우 각각의 정렬 대상이 최종 위치와 거리가 얼마나 떨어져 있느냐가 시간에 영향을 미치는데 , 버켓을 작게 만들면 거리 차이가 거의 안나게 되므로 optimal 하다고 볼 수 있다 . ) 라고 써있다.

bucket 을 나눌대는 최대한 각각의 bucket 에 비슷한 양이 분배되도록 하고 insertion sort 를 적용하면 거의 선형 시간에 sorting 할 수 있다. ( bucket 을 나누는게 중요하다. )  


 기타 살펴 볼 만한 소팅 
proxmap sort
histogram sort
counting sort
postman's sort
shuffle sort