버킷 정렬

1. 버킷 정렬 알고리즘
2. 버킷 정렬 예
3. 버킷 정렬 알고리즘 구현
4. 버킷 정렬 알고리즘 복잡성

버킷 정렬은 비교 유형 정렬 알고리즘입니다. 요소를 버킷 또는 빈에 배포하고 다른 알고리즘 (일반적으로 삽입 정렬)을 사용하여 개별 버킷의 콘텐츠를 정렬하여 요소를 정렬합니다. 그런 다음 개별 정렬 된 버킷을 함께 추가하여 최종 정렬 된 배열을 얻습니다. 이러한 정렬 알고리즘 접근 방식을 분산 수집 접근 방식이라고도합니다. 주로 입력이 0.00에서 1.00까지의 부동 소수점과 같은 범위에 걸쳐 균일하게 분포 될 때 사용됩니다.

버킷 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

버킷 정렬 예

배열이(0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31)이라고 가정합니다. 버킷 정렬 알고리즘을 사용하여 정렬합니다.

• 0.1 범위의 버킷10을 만듭니다.

• 버킷에 요소를 삽입하면 다음을 얻습니다.

• 개별 버킷 정렬 :

모든 결과를 함께 추가하면 최종 정렬 된 배열이(0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55)로 표시됩니다.

버킷 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

버킷 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

평균적인 경우는 요소가 무작위로 분포 된 경우 발생하며 알고리즘은 매우 효율적인 결과를 제공합니다. 시간 복잡도는 [Big Theta] :O(n + k)의 순서입니다. 평균 선형 시간 복잡도를 가진 몇 안되는 알고리즘 중 하나이며, 버킷 크기의 제곱의 합이 n에서 선형이면이 복잡도가 유지됩니다.

• 최악의 경우

최악의 경우는 많은 요소가 배열에서 가까운 범위에 있고 동일한 버킷에서 함께 클러스터 될 때 발생합니다. 입력을 버킷으로 나누는 모든 이점을 없애고 전체 복잡성은 사용 된 정렬 알고리즘에 따라 달라집니다. 삽입 정렬은 요소가 역순 일 때 최악의 경우 시간 복잡도가 O(n²)입니다. 따라서 최악의 시간 복잡도는 [Big O] : O(n²)입니다.

• 베스트 케이스

가장 좋은 경우는 요소가 모든 버킷에 균일하게 분포되어 있거나 이미 정렬 된 배열을 얻을 때 발생합니다. 총 시간 복잡성은 O(n)버킷을 만드는 데 필요한 시간과 O(k)를 정렬하는 데 필요한 시간으로 구성됩니다. 최적의 시간 복잡도는 [Big Omega] :O(n + k)입니다.

공간 복잡성

버킷 정렬 알고리즘의 최악의 경우 공간 복잡성은O(n * k)이며 여기서n은 요소 수이고k는 버킷 수입니다. 모든 요소를 보관할 공간을 줄이고 버킷 시작에 대한 포인터를 저장하여 공간 복잡성을O(n + k)로 줄일 수 있습니다.