버킷 정렬 알고리즘 (Bucket Sort)

버킷 정렬 알고리즘(Bucket Sort Algorithm)

정렬되지 않은 자료를 버킷이라는 단위 기억 장소에 여러 그룹으로 정렬하고 버킷별 키 값에 따라 다시 정렬하는 알고리즘

1. 사이즈 12의 정렬할 배열을 가정합니다. (size=12)
   

2. 크기가 6인 배열을 만듭니다. 이 배열의 각 요소는 버킷으로 사용합니다.
   

3. input 배열에서 버킷에 요소를 삽입합니다. 버킷의 범위에 따라 요소가 삽입됩니다.
   예를 들어, [11~15] 버킷에는 14, 15, 11가 들어가고, [16~20] 버킷에는 19, 16이 들어갑니다.
   

4. 각 버킷은 정렬 알고리즘(ex 퀵 정렬)을 사용하여 정렬합니다.
   

5. 각 버킷의 요소들을 모읍니다.
   

버킷 정렬 알고리즘 구현

아래 예제는 5를 기준으로 생성한 버킷을 가정합니다.

# python 3.8

def bucket_sort(arr):
    # 2. create buckets
    bucket = create_bucket(min(arr), max(arr))
    # 3. insert element into buckets
    bucket = insert_into_bucket(arr, bucket)
    # 4. sort the elements of each bucket
    bucket = sort_bucket(bucket)
    # 5. get the sorted elements
    answer = gather(bucket)
    return answer
    
   def create_bucket(min_element, max_element):
    min_quotient = min_element // 10
    max_quotient = max_element // 10
    len_bucket = (max_quotient - min_quotient + 1) * 2
    bucket = [[] for i in range(len_bucket)]
    return bucket


def insert_into_bucket(arr, bucket):
    for i in arr:
        quotient = i // 10
        remainder = i % 10
        bucket_index = quotient * 2
        if remainder > 5:
            bucket_index += 1
        bucket[bucket_index].append(i)
    return bucket


def sort_bucket(bucket):
    for i in range(len(bucket)):
        bucket[i] = sorted(bucket[i])
    return bucket


def gather(bucket):
    answer = []
    for a in bucket:
        for e in a:
            answer.append(e)
    return answer

github : https://github.com/honeybeeveloper/algorithm/blob/develop/bucket-sort.py
참고 : https://www.programiz.com/dsa/bucket-sort
참고 : 책 <그림으로 정리한 알고리즘과 자료구조>