버킷 정렬

버킷 정렬은 비교 유형 정렬 알고리즘입니다. 요소를 버킷 또는 빈에 배포하고 다른 알고리즘 (일반적으로 삽입 정렬)을 사용하여 개별 버킷의 콘텐츠를 정렬하여 요소를 정렬합니다. 그런 다음 개별 정렬 된 버킷을 함께 추가하여 최종 정렬 된 배열을 얻습니다. 이러한 정렬 알고리즘 접근 방식을 분산 수집 접근 방식이라고도합니다. 주로 입력이 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)로 줄일 수 있습니다.