バケットソートアルゴリズム（Java, Python、C/C++ コード例

バケットソートとは何ですか?

バケット ソート (ビン ソートとも呼ばれます) は、ソートされていない配列を入力として受け入れ、結果としてソートされた配列を生成する比較ソート方法です。 この方法は、要素を複数のバケットに分散し、挿入ソートなどのソート アルゴリズムによって各バケットを個別にソートすることで機能します。 次に、すべてのバケットがマージされて、ソートされた配列が形成されます。

バケット ソートは、要素が次のような場合によく使用されます。

1. 浮動小数点値
2. 範囲全体に均一に分布

バケットソートの時間計算量は、使用されるバケットの数と入力分布の均一性に依存します。 シェルソート、マージソート、ヒープソート、および クイックソート 最良ケースの時間計算量は O(n*logn) ですが、バケット ソート アルゴリズムでは線形時間計算量または O(n) で同じことが達成できます。

バケットソートは、スキャッターギャザーアプローチに従います。このアプローチを適用すると、要素は対応するバケットに分散され、バケット内でソートされ、最終ステップとしてソートされた配列を形成するために集められます。このスキャッターギャザーアプローチについては、次のセクションで説明します。

スキャッター・ギャザリング・アプローチ

大規模で複雑な問題は、解決が難しい場合があります。分散収集アプローチでは、データ セット全体をクラスターに分割して、このような問題を解決します。次に、各クラスターを個別に処理し、すべてをまとめて最終的な答えを出します。

バケット ソート アルゴリズムがスキャッター ギャザー メソッドを実装する方法は次のとおりです。

バケットソートの仕組み

バケットソートの基本的な動作原理は次のとおりです。

1. 空のバケットのセットが作成されます。 異なるポリシーに基づいて、バケットの数は異なる場合があります。
2. 入力配列から、各要素を対応するバケットに入れます。
3. それらのバケットを個別に並べ替えます。
4. ソートされたバケットを連結して、単一の出力配列を作成します。

詳細な作業手順については、次のセクションで説明します。

擬似コード

Start
Create N empty buckets
For each array element:
Calculate bucket index
Put that element into the corresponding bucket
For each bucket:
Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

方法 1: 浮動小数点のバケット ソート アルゴリズム Numbers

0.0 から 1.0 までの範囲内の浮動小数点数のバケット ソート アルゴリズム:

ステップ1） 最初のバケットに [10, 0.0) の範囲内の数値が含まれるように 0.1 個の空のバケットを作成します。次に、0.1 番目のバケットに [0.2, XNUMX) の範囲内の数値が含まれるようにします。

ステップ2） 各配列要素について:

ａ． 次の式を使用してバケット インデックスを計算します。
バケットインデックス = no_of_buckets *array_element

b. 要素をバケット[bucket_index]に挿入します

ステップ3） 挿入ソートを使用して各バケットを個別にソートします。

ステップ4） すべてのバケットを単一の配列に連結します。

バケットソートの例を見てみましょう。この例では、バケットソートアルゴリズムを使用して次の配列をソートします。

ステップ1） まず、10 個の空のバケットを作成します。最初のバケットには [0.0, 0.1) の間の数字が含まれ、0.1 番目のバケットには [0.2, XNUMX) の間の数字が含まれます。

ステップ2） 配列要素ごとにバケット インデックスを計算し、要素をそのバケットに配置します。

バケット インデックスは、次の式を使用して計算できます。
              bucket_index= no_of_buckets*array_element

バケットインデックスの計算:
a）0.78
      Bucket_index = no_of_buckets*array_element
                   = 10 * 0.78
                   = 7.8
したがって、要素 0.78 はバケット[floor(7.8)] またはバケット[7] に格納されます。

b）0.17
      bucket_index = no_of_buckets * 配列要素
                   = 10 * 0.17
                   = 1.7

配列要素 0.17 は、bucket[floor(1.7)] または Bucket[1] に格納されます。

c）の0.39
      bucket_index = no_of_buckets * 配列要素
                   = 10 * 0.39
                   = 3.9
   0.39 はバケット[フロア(3.9)]またはバケット[3]に保存されます。

すべての配列要素を反復処理した後、バケットは次のようになります。

ステップ3） 次に、各バケットは挿入ソートを使用してソートされます。ソート操作後の出力は次のようになります。

ステップ4） 最後のステップでは、バケットが単一の配列に連結されます。 その配列は、入力のソート結果になります。

各バケットは出力配列に連結されます。 たとえば、XNUMX 番目のバケット要素を連結すると次のようになります。

最後のバケット要素の連結は次のようになります。

連結後の結果の配列は、目的のソートされた配列になります。

C言語でのバケットソートプログラム/C++

入力：

//Bucket Sort Program in C/C++
//For not having integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
 bucket[index].push_back(input[i]);
  }
for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
 int array_size = sizeof(input)/sizeof(input[0]);
 
 bucketSort(input, array_size);
 cout <<"Sorted Output: \n";
 for (int i = 0; i< array_size; i++)
 cout<<input[i]<<" ";
return 0;
}

出力：

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

バケットソートプログラム Python

入力：

# Bucket Sort Program in Python
# For not having integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

出力：

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

バケットソート Java

入力：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List <
        Float >
        [] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList < >
                ();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
               }
            }
        }
    }
    public static void main(String[] args) {
    float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

出力：

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

方法 2: 整数要素のバケット ソート アルゴリズム

[0.0, 1.0]の範囲を超える数値を含む入力に対するバケットソートアルゴリズムは、以前のものとは少し異なります。 アルゴリズム。 この場合に必要な手順は次のとおりです。

ステップ1） 最大要素と最小要素を見つけます。

ステップ2） バケットの数 n を選択し、それらのバケットを空として初期化します。

ステップ3） 次の式を使用して、各バケットの範囲またはスパンを計算します。
               span = (maximum - minimum)/n

ステップ4） 各配列要素について:

1.バケットインデックスを計算します。
               bucket_index = (element - minimum)/span

2.バケット[bucket_index]に要素を挿入します。

ステップ5） 挿入ソートを使用して各バケットをソートします。

ステップ6） すべてのバケットを単一の配列に連結します。

このバケットソートアルゴリズムの例を見てみましょう。この例では、バケットソートアルゴリズムを使用して次の配列をソートします。

ステップ1） 最初のステップでは、指定された配列の最大要素と最小要素を見つける必要があります。 この例では、最大値は 24、最小値は 1 です。

ステップ2） ここで、空のバケットの数 n を選択する必要があります。 この例では、5 つのバケットを使用します。 次に、それらを空として初期化します。

ステップ3） 各バケットのスパンは次の式で計算する必要があります。
               span = (maximum-minimum)/n = (24-1)/5 = 4;

したがって、最初のバケットには [0, 5) の範囲内の数字が含まれ、5 番目のバケットには [10, XNUMX) の範囲内の数字が含まれます。

ステップ4） 配列要素ごとにバケット インデックスを計算し、要素をそのバケットに配置します。 バケット インデックスは、次の式を使用して計算できます。
               bucket_index = (element - minimum)/span

バケットインデックスの計算:

a) 11bucket_index = (要素 – 最小値)/スパン
                   =（11-1）/ 4
                   =2

したがって、要素 11 はバケット [2] に格納されます。

b）9
bucket_index = (要素 – 最小値)/スパン
                   =（9-1）/ 4
                   =2

注意： 9 は、bucket[1] の境界要素であるため、前の要素と同じバケットに追加するのではなく、bucket[1] に追加する必要があります。

各要素に対して操作を実行すると、バケットは次のようになります。

ステップ5） ここで、各バケットは挿入ソートを使用してソートされます。 仕分け後のバケツ

ステップ6） 最後のステップでは、バケットが単一の配列に連結されます。 それ 配列 入力のソート結果になります。

C言語でのバケットソートプログラム/C++

入力：

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>>
  output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>
      ());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     -
      int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1]
      .push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(
        input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double>
  input ={11,9,21,8,17,19,13,1,24,12
  };
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<
  "Sorted Output:";
  for (int i; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

出力：

Sorted Output:1 8 9 11 12 13 17 19 21 24

バケットソートプログラム Python

入力：

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:\n", input)

出力：

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

バケットソート Java

入力：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List <
        List <
        Double > >
        output = new ArrayList < >
        ();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList < >
                ());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
				}
			}
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
			Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double>
        input = new ArrayList <>
        ();
        input.add(11.0);
		input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
		System.out.print(value + " ");
        }
    }
}

出力：

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

長所と短所

メリット	デメリット
より高速な計算を実行する	他のアルゴリズムに比べて多くのスペースを消費する
外部ソート方法として使用できます	データが均一に分散されていない場合、パフォーマンスが低下します
バケットは個別に処理可能

バケットソートの複雑性分析

バケットソートの時間計算量

• 最良のケースの複雑さ:すべての配列要素が均一に分散され、事前にソートされている場合、要素を対応するバケットに分散するには O(n) 時間がかかります。 次に、次を使用して各バケットを並べ替えます 挿入ソート コストはO(k)になります。したがって、全体的な複雑さはO(n+k)になります。

• 平均的なケースの複雑さ:平均的なケースでは、入力は均一に分散されていると仮定します。したがって、バケット ソート アルゴリズムは、線形時間計算量 O(n+k) を実現します。ここで、要素を分散するには O(n) 時間が必要であり、挿入ソートを使用してそれらの要素をソートするには O(k) 時間が必要です。

• 最悪の場合の複雑さ:最悪の場合、要素は均一に分散されず、XNUMX つまたは XNUMX つの特定のバケットに集中します。 その場合、バケットソートは次のように機能します。 バブルソートアルゴリズム。 したがって、最悪の場合、バケットソートの時間計算量は O(n^2) になります。

バケットソートの空間計算量

バケットソートの空間計算量は O(n*k) です。ここで、n は要素の数、k は必要なバケットの数です。