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

버킷 정렬 (Bucket Sort)

버킷 정렬은 데이터를 여러 개의 그룹(버킷)으로 나눈 후, 각 버킷을 정렬하여 최종적으로 병합하는 정렬 알고리즘입니다. 주로 데이터가 균등하게 분포되어 있을 때 효율적으로 작동하며, 연속적인 값의 정렬에 적합합니다.

---

1. 동작 원리

1. 버킷 생성: 정렬할 데이터 범위를 기준으로 여러 개의 버킷을 생성합니다.
2. 데이터 분배: 각 데이터를 해당 값에 적합한 버킷에 삽입합니다.
3. 버킷 정렬: 각 버킷 내부에서 정렬 알고리즘(보통 삽입 정렬 또는 퀵 정렬)을 사용해 정렬합니다.
4. 병합: 모든 버킷의 데이터를 순서대로 병합하여 최종적으로 정렬된 배열을 만듭니다.

---

2. 특징

• 시간 복잡도:
  • 평균: O(n + k) (여기서 kk는 버킷의 개수)
  • 최악: O(n^2) (모든 데이터가 한 버킷에 들어가는 경우)
• 공간 복잡도: O(n + k) (입력 데이터와 버킷 저장 공간)
• 안정성: 안정 정렬이 아니지만, 특정 구현으로 안정성을 보장할 수 있음.
• 적용 범위:
  • 실수 또는 균등하게 분포된 데이터를 정렬하는 데 적합합니다.
  • 데이터가 균등하게 분포되지 않으면 성능이 저하될 수 있음.

---

3. 정렬 과정

예제 배열: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

1. 버킷 생성:
   • 배열의 값 범위(0~1)를 기준으로 10개의 버킷 생성.
2. 데이터 분배:
   • 각 데이터를 버킷에 삽입.
   • 예:
     • 0.78 → 버킷 7
     • 0.17 → 버킷 1
     • ...
   결과:
3. 버킷 0: [0.12] 버킷 1: [0.17, 0.21, 0.23] 버킷 2: [0.26] 버킷 3: [0.39] 버킷 6: [0.68] 버킷 7: [0.72, 0.78] 버킷 9: [0.94]
4. 버킷 정렬:
   • 각 버킷 내부를 정렬(삽입 정렬 사용).
5. 병합:
   • 정렬된 버킷을 순서대로 병합.
   • 최종 결과: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

---

4. 장단점

장점:

1. 빠른 정렬 가능: 데이터가 균등하게 분포된 경우 O(n + k)의 성능을 보임.
2. 간단한 로직: 데이터 분할 후 각 그룹을 독립적으로 정렬.

단점:

1. 추가 메모리 필요: 버킷 저장 공간이 추가로 필요함.
2. 분포 의존적: 데이터가 고르게 분포되지 않으면 성능이 저하될 수 있음.
3. 최적 버킷 수 필요: 적절한 버킷 수와 크기를 설정하는 것이 중요함.

---

5. Java 구현

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

public class BucketSort {

    public static void bucketSort(float[] arr) {
        int n = arr.length;

        // 1. 버킷 초기화
        ArrayList<Float>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 2. 데이터 분배 (각 값에 해당하는 버킷에 추가)
        for (float num : arr) {
            int bucketIndex = (int) (num * n); // 범위에 따라 버킷 인덱스 계산
            buckets[bucketIndex].add(num);
        }

        // 3. 각 버킷 정렬
        for (ArrayList<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 4. 버킷 병합
        int index = 0;
        for (ArrayList<Float> bucket : buckets) {
            for (float num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        float[] arr = {0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f};
        System.out.println("원본 배열:");
        for (float num : arr) {
            System.out.print(num + " ");
        }

        bucketSort(arr);

        System.out.println("\n정렬된 배열:");
        for (float num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

6. Python 구현

def bucket_sort(arr):
    n = len(arr)
    if n <= 0:
        return arr

    # 1. 버킷 초기화
    buckets = [[] for _ in range(n)]

    # 2. 데이터 분배 (각 값에 해당하는 버킷에 추가)
    for num in arr:
        bucket_index = int(num * n)  # 범위에 따라 버킷 인덱스 계산
        buckets[bucket_index].append(num)

    # 3. 각 버킷 정렬
    for bucket in buckets:
        bucket.sort()

    # 4. 버킷 병합
    sorted_array = []
    for bucket in buckets:
        sorted_array.extend(bucket)

    return sorted_array


# 예제 실행
if __name__ == "__main__":
    arr = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
    print("원본 배열:", arr)

    sorted_arr = bucket_sort(arr)

    print("정렬된 배열:", sorted_arr)

---

7. 언제 사용해야 하나?

1. 실수 정렬:
   • 데이터가 0과 1 사이에 균등하게 분포된 경우 이상적.
2. 큰 데이터셋:
   • 정렬해야 할 데이터셋이 클수록 성능의 이점이 커질 수 있음.
3. 특정 분포 데이터:
   • 값이 고르게 퍼져 있는 경우 빠른 성능을 기대할 수 있음.

버킷 정렬은 특정 시나리오에서 매우 효과적이지만, 데이터 분포와 버킷 크기 설정에 따라 성능이 크게 달라질 수 있으므로 주의가 필요합니다.