버킷 정렬(Bucket Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 장단점, 주의점

버킷 정렬(Bucket Sort) 총 정리

 

 

버킷 정렬은 데이터를 여러 개의 "버킷"으로 나누고 각 버킷에 저장된 데이터를 정렬한 뒤, 이를 합쳐 최종 정렬을 완성하는 분산 기반 정렬 알고리즘입니다. 데이터가 균등 분포되어 있을수록 높은 효율을 발휘하며, 비교 기반 정렬보다 더 빠를 수 있습니다.

---

 

 

1. 버킷이란?

버킷에 대한 자세한 개념은 아래 글에 상세한 예시와 함께 작성했습니다. 버킷 자체만으로도 코딩 테스트에 자주 나오는 개념이라 꼭 숙지하는 것이 중요합니다.

2024.12.20 - [알고리즘] - 버킷(Bucket) 알고리즘 - 코딩테스트에서 시간을 단축하는 비법(시간복잡도, C언어,Java,Python 예시코드)

버킷(Bucket) 알고리즘 - 코딩테스트에서 시간을 단축하는 비법(시간복잡도, C언어,Java,Python 예시코

 

 

2. 원리

1. 데이터를 특정 범위를 기준으로 여러 개의 버킷으로 나눕니다.
2. 각 버킷 내부의 데이터를 정렬합니다 (종종 삽입 정렬, 병합 정렬, 혹은 다른 정렬 알고리즘 사용).
3. 정렬된 버킷을 합칩니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [78, 17, 39, 26, 72, 94, 21, 12, 23, 68]

1. 버킷 분배:
   • 데이터의 최대값을 기준으로 각 버킷의 범위를 정의합니다.
   • 여기서는 최대값이 100이라고 가정하고, 각 버킷의 범위를 10으로 설정합니다.
   • 분배 결과:
     • 버킷 0: [12]
     • 버킷 1: [17]
     • 버킷 2: [21, 23, 26]
     • 버킷 3: [39]
     • 버킷 6: [68]
     • 버킷 7: [72, 78]
     • 버킷 9: [94]
2. 각 버킷 내부 정렬:
   • 각 버킷 내부는 삽입 정렬(Insertion Sort)로 정렬합니다.
     • 버킷 0: [12] (이미 정렬 완료)
     • 버킷 1: [17] (이미 정렬 완료)
     • 버킷 2: [21, 23, 26] (삽입 정렬 수행)
     • 기타 버킷도 정렬 수행.
   • 삽입 정렬의 시간 복잡도는 O(k²)이며, 여기서 k는 각 버킷에 포함된 데이터 개수입니다.
3. 버킷 병합:
   • 병합 결과: [12, 17, 21, 23, 26, 39, 68, 72, 78, 94]
4. 최종 정렬 완료:
   • 결과: [12, 17, 21, 23, 26, 39, 68, 72, 78, 94]

반응형

---

 

 

4. 시간 복잡도

• 평균 시간 복잡도: O(n + k)
  • n: 데이터 개수
  • k: 버킷 개수
• 최악 시간 복잡도: O(n²) (모든 데이터가 하나의 버킷에 몰릴 경우)
• 공간 복잡도: O(n + k)

각 버킷 내부의 정렬은 삽입 정렬로 구현되는 경우가 많으며, 평균적으로 O(k²)의 시간 복잡도를 가집니다. 하지만 각 버킷에 들어가는 데이터 개수(k)가 작을수록 효율적입니다.

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>
#include <stdlib.h>

void bucketSort(int arr[], int n) {
    int max = 100;
    int bucketRange = 10;
    int bucketCount = max / bucketRange;

    int *buckets[bucketCount];
    int count[bucketCount];

    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = (int *)malloc(n * sizeof(int));
        count[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int index = arr[i] / bucketRange;
        buckets[index][count[index]++] = arr[i];
    }

    for (int i = 0; i < bucketCount; i++) {
        for (int j = 1; j < count[i]; j++) {
            int key = buckets[i][j];
            int k = j - 1;

            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }
    }

    int idx = 0;
    for (int i = 0; i < bucketCount; i++) {
        for (int j = 0; j < count[i]; j++) {
            arr[idx++] = buckets[i][j];
        }
    }

    for (int i = 0; i < bucketCount; i++)
        free(buckets[i]);
}

int main() {
    int arr[] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68};
    int n = sizeof(arr) / sizeof(arr[0]);

    bucketSort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

 

Java 코드

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

    public static void bucketSort(int[] arr, int max) {
        int bucketRange = 10;
        int bucketCount = max / bucketRange;
        ArrayList<Integer>[] buckets = new ArrayList[bucketCount];

        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (int num : arr) {
            int index = num / bucketRange;
            buckets[index].add(num);
        }

        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        int idx = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[idx++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68};

        bucketSort(arr, 100);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

Python 코드

def bucket_sort(arr, max_val):
    bucket_range = 10
    bucket_count = max_val // bucket_range
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        index = num // bucket_range
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    result = []
    for bucket in buckets:
        result.extend(bucket)

    return result

arr = [78, 17, 39, 26, 72, 94, 21, 12, 23, 68]
arr = bucket_sort(arr, 100)
print(arr)

---

 

 

6. 주의점

1. 데이터가 균등하게 분포되어 있어야 높은 효율성을 발휘합니다.
2. 버킷의 개수와 범위를 적절히 설정하지 않으면 성능이 저하될 수 있습니다.
3. 각 버킷 내부의 정렬 알고리즘 선택이 중요합니다. 삽입 정렬은 데이터 개수가 적을 경우 효율적입니다.

---

 

 

7. 장단점

장점

• O(n)의 시간 복잡도로 매우 빠름.
• 대량의 데이터를 효과적으로 처리 가능.

단점

• 데이터의 분포가 균등하지 않으면 비효율적.
• 추가 메모리 사용량이 많음.
• 버킷 내부 정렬로 인한 추가 연산.

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주