[파이썬 자료구조] 버킷정렬(bucket sort)

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

key의 범위를 알려진 경우에만 사용가능한 정렬방식임

키의 값을 새로운 배열의 인덱스로 사용함

파이썬으로 구현해봄

def bucket_sort(keys, low, high):
    length = high - low + 1 # length of buckets
    bucket = [[] for _ in range(length)]
    keys_sorted = []
 
    for elem in keys:
        bucket[elem-low].append(elem)
 
    for idx in range(length):
        while len(bucket[idx]):
            keys_sorted.append(bucket[idx].pop(0))
 
    return keys_sorted

low와 high는 키의 범위이고 length는 범위의 길이입니다. bucket은 2차원 배열로 length의 크기만큼으로 초기화했음

keys_sorted는 결과를 넣을때 사용할꺼임 일단 비워둠

6, 7번째 줄에서 bucket에다가 키의 값을 넣음

9,10,11번에서 bucket에서 하나씩 꺼내서 keys_sorted에 넣으면 끝임

시간복잡도를 알아보자

9번째 줄에서 길이만큼 반복하니까 일단 O(n)임 (왜냐면 n개에 대해서 수행하니까)

10번째 줄에서는 k개 만큼 수행하니까 O(k)임 (9번째줄은 범위의 길이고 10번째줄은 버컷의 길이임)

따라서 평균복잡도는 O(n+k)임

최악의 경우는 하나의 범위안에 다들어가 있는 경우임

이때는 O(n^2)의 수행시간을 가지므로 시간복잡도는 O(n^2)임