버킷정렬

버킷정렬이란

버킷 정렬(Bucket Sort)은 요소들을 미리 정해진 "버킷"(또는 구간)에 나누어 담고, 각 버킷 안의 요소(element)들을 개별적으로 정렬한 후 다시 합치는 정렬 알고리즘입니다. 이 알고리즘은 일반적으로 원소들이 특정 범위 내에 균등하게 분포되어 있을 때 가장 효율적으로 동작합니다.

작동방식

1. 버킷 생성: 정렬하려는 원소들의 값 범위를 미리 알고, 이 범위에 따라 적절한 개수의 버킷을 생성합니다.

2. 원소 분배: 모든 원소를 해당하는 버킷에 분배합니다. 이 때, 분배하는 방식은 일반적으로 다음과 같습니다.

• 원소의 값 범위를 전체 버킷 개수로 나누어 그 값에 해당하는 버킷을 찾습니다.
• 예를 들어 값 범위가 0에서 100이고, 10개의 버킷을 사용한다면 0 ~ 9, 10 ~ 19, 20 ~ 29...90 ~ 99, 100으로 10개의 버킷이 생성합니다.
• 각 원소를 적절한 버킷에 넣습니다.

3. 버킷별 정렬: 각 버킷에 들어있는 원소들을 개별적으로 정렬합니다. 이 부분은 다른 정렬 알고리즘, 예를 들어 삽입 정렬(Insertion Sort)이나 퀵 정렬(Quick Sort) 등을 사용할 수 있습니다.

4. 버킷 병합: 정렬된 각 버킷들을 순서대로 합쳐서 최종적으로 정렬된 결과를 얻습니다.

시간 복잡도

버킷 정렬의 시간 복잡도는 대부분의 경우 O(n) ~ O(n^2) 사이입니다. 원소들이 특정 범위 내에 균등하게 분포되어 있을 때는 매우 효율적이지만, 값의 범위가 크고 원소들이 한 버킷에 몰려있는 경우 성능이 저하될 수 있습니다. 따라서 버킷 정렬을 사용할 때는 적절한 버킷 크기와 버킷 개수를 선택하는 것이 중요합니다.

코드

def bucket_sort(arr):
    # 입력된 리스트에서 최댓값과 최솟값을 찾습니다.
    min_val = min(arr)
    max_val = max(arr)

    # 최댓값과 최솟값 사이의 범위를 계산합니다.
    bucket_range = (max_val - min_val) / len(arr)

    # 빈 버킷 리스트를 생성합니다.
    buckets = [[] for _ in range(len(arr))]

    # 입력 리스트의 원소를 버킷에 분배합니다.
    for num in arr:
        index = int((num - min_val) // bucket_range)
        buckets[index].append(num)

    # 각 버킷을 개별적으로 정렬합니다.
    for i in range(len(buckets)):
        buckets[i].sort()

    # 정렬된 버킷들을 합쳐서 최종 결과 리스트를 생성합니다.
    sorted_arr = []
    for bucket in buckets:
        sorted_arr += bucket

    return sorted_arr


input_list = [29, 25, 10, 8, 17, 4, 2]
result = bucket_sort(input_list)
print(result)