Bucket Sort (버킷 정렬)

버킷 정렬이란?

bucket은 바구니를 의미합니다. 

말 그래도 버킷 정렬은 바구니에 데이터를 담는 형태를 닮았다 하여 이름 붙여졌습니다.

위 그림과 같이 숫자를 카테로리별로 나눠 바구니에 담은 뒤,

그 바구니 안을 정렬해주는 방식입니다.

 

바구니 안을 정렬할 때는 앞에서 배웠던 정렬 방식 중 아무거나 사용하셔도 상관 없습니다.

 

저는 삽입 정렬을 이용해서 버킷 정렬을 구현해보았습니다.

 

 

코드)

디버깅, 실행할 때 보기 편하도록 

버킷을 출력해주는 함수를 추가해주었습니다.

#include <iostream>
#include <vector>

void Print(std::vector<float>& v) {
  for (auto& a : v) {
    std::cout << a << " ";
  }
  std::cout << '\n';
}

void PrintBucket(std::vector<std::vector<float>>& v) {
  for (int i = 0; i < v.size(); i++) {
    std::cout << i << ": ";
    for (int j = 0; j < v[i].size(); j++) {
      std::cout << v[i][j] << " ";
    }
    std::cout << '\n';
  }
}

void InsertionSort(std::vector<float>& v) {
  for (int i = 0; i < v.size(); i++) {
    float key = v[i];
    int j = i - 1;
    while (j >= 0 && v[j] > key) {
      v[j + 1] = v[j];
      j--;
    }
    v[j + 1] = key;
  }
}

void BucketSort(std::vector<float>& v, int num_buckets) {
  std::vector<std::vector<float>> buckets(num_buckets);

  for (auto a : v) {
    int idx = int(num_buckets * a);
    buckets[idx].push_back(a);
  }

  std::cout << "Before sorting" << '\n';
  PrintBucket(buckets);

  for (int i = 0; i < num_buckets; i++) {
    InsertionSort(buckets[i]);
  }

  std::cout << "After sorting" << '\n';
  PrintBucket(buckets);

  int index = 0;
  for (int i = 0; i < num_buckets; i++) {
    for (auto j : buckets[i]) {
      v[index++] = j;
    }
  }
}

 

10의자릿수대로 분류해주고 각 바구니를 정렬해주는 방식이라 구현은 어렵지 않게 할 수 있을 것 같습니다.

 

버킷 정렬의 시간 복잡도)

 

이를 이해하기 위해서는 기댓값과 분산에 대한 이해가 필요하다.

 

-기댓값과 분산의 상관관계

 

위와 같이 기댓값으로부터 분산을 구할 수 있습니다.

 

이것 말고도 이항분포에 대한 간단한 이해도 필요합니다.

 

 

 

-이항 분포

위의 기댓값과 분산을 구하는 것은 X가 이항분포 n,p를 따를 때의 성질을 이용한 것입니다.

 

 

이제는 시간 복잡도에 대해 알아보도록 하겠습니다.

 

-평균 시간

버킷의 개수와 입력의 개수 모두 n개라고 가정했을 때 평균 시간복잡도는 𝜭(n)인 것을 확인할 수 있습니다.

 

그렇다면 최악의 경우는 어떨까요??

 

만약 모든 입력의 카테고리가 같아서 모두 하나의 바구니로 들어간다면 어떨까요?

 

그럴 때는 그냥 한 바구니에 있는 전체 데이터를 정렬해주는 것이므로 다른 정렬과 다를 바가 없습니다.

 

따라서 최악의 경우에는 O(n^2) 이라고 할 수 있습니다.