그림으로 알아보는 버킷 정렬 (bucket sort)

버킷 정렬

해싱과 매우 비슷합니다.

적당한 기준으로 나누고 각 부분들을 또 다른 알고리즘으로 정렬한 뒤 순서에 맞게 합칩니다.

---

시간 복잡도

혼자서는 사용되지 않고 다른 알고리즘과 함께 사용되기 때문에,

같이 사용되는 다른 알고리즘에 의하여 시간 복잡도가 결정됩니다.

---

Worst Case는 모든 데이터가 하나의 버킷에 들어가는 것이고,

Best Case는 모두 균등하게 분배되는 것입니다.

---

정렬 예제

[99, 57, 14, 23, 55, 77]을 정렬해보겠습니다.

---

먼저 적당히 여러개의 버킷으로 나누고 적당히 버킷의 룰을 결정합니다.

룰은 정말로 적당히 정하는데 해싱으로 나눌수도 있고 범위일수도 있습니다.

---

여기서는 범위를 기반으로 3개의 버킷으로 나눠서 [14, 23], [57, 55], [99, 77]로 분배되었습니다. 왼쪽부터 버킷에 차례대로 집어넣었기 때문에 각 버킷은 정렬되지 않은 상태입니다.

---

이제 여기서 다른 알고리즘을 사용하여 각 버킷을 정렬하고 정렬된 버킷을 적당히 병합하면 [14, 23, 55, 57, 77, 99]가 완성됩니다.