[자료구조] 버킷 정렬(Bucket Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

버킷 정렬(Bucket Sort)

개념

• 버킷 정렬은 주어진 배열을 범위를 나눠서 여러 개의 버킷(빈)으로 나누어 담은 뒤 각각의 버킷을 정렬하는 방식입니다. 
  • 각각의 버킷에 기존의 정렬 알고리즘을 적용하여 정렬을 진행합니다. 따라서 Non-comparison 기반 정렬이면서, comparison 기반 정렬이 됩니다.
• 버킷 정렬은 데이터가 균등하게 분포되어 있을때 최적의 성능을 발휘합니다. 데이터가 버킷에 고르게 분포되면 각 버킷 내의 데이터는 적고, 이는 각 버킷을 빠르게 정렬할 수 있음을 의미합니다. (여기서 중요한 점은 데이터가 특정 범위에 국한되어야 합니다. 그래야 일정한 범위로 각 버킷을 나눌 수 있습니다.)
  • 만약 버킷이 균등하게 분포되지 않는다면 결국에는 기존 정렬의 시간복잡도인 O(NlogN)과 동일해집니다. (버킷의 정렬알고리즘의 시간복잡도가 O(NlogN)을 사용한 경우)
  • 처음에 버킷으로 분배했을때 한 버킷에 모든 데이터가 들어가게 된다면 결국 그 한 버킷이 전체 데이터가 되기 때문에 기존의 전체 데이터를 정렬하는 것과 동일합니다.
  • 데이터가 균등하게 분포되어 있을 경우라면 각 버킷 별로 데이터가 대략 (n/k)개씩 들어가게 될 것입니다. 이럴 경우 전체 시간복잡도는 O(k * (n/k)log(n/k)) = O(nlog(n/k)) 가 될 것입니다. k를 적절한 크기로 설정을 해주게 되면 결국에는 log(n/k)가 상수처럼 취급되어 전체 시간은 O(n)만에 정렬된다고 생각할 수 있습니다.

코드

• Bucket Sort

  • def bucket_sort(arr, k):
        buckets = [[] for _ in range(k)]
    
        shift = min(arr)
        max_val = max(arr) - shift
    
        bucket_size = max(1, max_val / k)
    
        for i, item in enumerate(arr):
            index = int((item - shift) // bucket_size)
            if index == k:
                buckets[k - 1].append(item)
            else:
                buckets[index].append(item)
    
        for bucket in buckets:
            bucket.sort()
    
        sorted_arr = []
        for bucket in buckets:
            sorted_arr.extend(bucket)
    
        for i in range(len(arr)):
            arr[i] = sorted_arr[i]
    
    
    arr = [907, 256, 336, 736, 443, 831]
    bucket_sort(arr, 3)
    print(arr)

출처

• https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4439/