バケットソート

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) です。これは平均的な線形時間複雑度を持つ数少ないアルゴリズムの 1つであり、バケットサイズの 2 乗の和が n で線形である場合にこの複雑度を保持します。

• 最悪のケース

最悪のケースは、配列の中で多くの要素が近い範囲にあり、同じバケットにクラスタ化されてしまう場合に発生します。これは、入力をバケットに分割する利点をすべて奪い、全体の複雑さは使用するソートアルゴリズムに依存することになります。挿入ソートは、要素の順序が逆の場合、最悪の場合の時間的複雑さは O(n²)です。したがって、最悪の時間的複雑さは [Big O]となります。O(n²)となります。

• 最良のケース

最良のケースは、要素がすべてのバケットに一様に分散している場合、あるいは既にソートされた配列が得られる場合です。総時間複雑度は、バケット O(n) を作成するのに必要な時間と、O(k) をソートするのに必要な時間からなります。最良の場合の時間的複雑度は [Big Omega]: O(n+k) です。

空間計算量

バケットソートアルゴリズムの最悪の場合の空間複雑度は O(n*k) であり、n は要素数、k はバケットの数です。すべての要素を保持するための空間を減らし、バケットの開始点へのポインタを格納することで、空間の複雑さを O(n+k) に減らすことができます。