버킷(Bucket) 정렬(개념, 시간 복잡도)

1. 버킷 정렬

버킷 정렬 또는 버킷 소트(bucket sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬 알고리즘이다. 각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다.

버킷의 정렬은 다음과 같이 이루어진다:

1. 처음에 비어있는 버킷들의 배열을 배치한다.
2. 분산: 원래의 배열을 살펴보고 각 객체를 버킷에 담는다.
3. 비어있지 않은 각 버킷을 정렬한다.
4. 수집: 순서대로 버킷을 방문하여 모든 요소를 원래의 배열에 위치시켜 놓는다.

 

내 해석 : 농작물을 분류할때 크기 별로 분류하듯이 첫번재 버킷에 크기 별로 분류하여 정렬하는 알고리즘

출처 : https://ko.wikipedia.org/wiki/%EB%B2%84%ED%82%B7_%EC%A0%95%EB%A0%AC

 

 

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

1. 배열의 첫번째 부터 자리에 맞는 버킷에 넣음

2. 버킷을 정렬

3. 첫번째 버킷 부터 정렬된 숫자를 배열에 넣음

 

시간 복잡도

O(n+k)

버킷 정렬은 혼자 쓰이지 않고 버킷을 정렬하기 위해 다른 알고리즘과 함께 사용된다.