logo

TechCodeview

バケット ソート – データ構造とアルゴリズムのチュートリアル

バケットソート 要素をさまざまなグループまたはバケットに分割するソート手法です。これらのバケットは、要素を均一に分散することによって形成されます。要素がバケットに分割されると、他の並べ替えアルゴリズムを使用して要素を並べ替えることができます。最後に、ソートされた要素が順序どおりにまとめられます。

Java マップ

バケットソートアルゴリズム:

作成する n 空のバケット (またはリスト) を作成し、すべての配列要素 arr[i] に対して次の操作を実行します。



  • arr[i] をバケット [n*array[i]] に挿入します
  • 挿入ソートを使用して個々のバケットをソートします。
  • ソートされたすべてのバケットを連結します。

バケットソートはどのように機能しますか?

入力配列にバケットソートを適用するには [0.78、0.17、0.39、0.26、0.72、0.94、0.21、0.12、0.23、0.68] 、次の手順に従います。

ステップ1： 各スロットがバケットを表す、サイズ 10 の配列を作成します。

並べ替え用のバケットの作成

並べ替え用のバケットの作成



ステップ2： 範囲に基づいて入力配列からバケットに要素を挿入します。

バケットへの要素の挿入:

  • 入力配列から各要素を取得します。
  • 要素にバケット配列のサイズを掛けます (この場合は 10)。たとえば、要素 0.23 の場合、0.23 * 10 = 2.3 が得られます。
  • 結果を整数に変換すると、バケット インデックスが得られます。この場合、2.3 は整数 2 に変換されます。
  • 計算されたインデックスに対応するバケットに要素を挿入します。
  • 入力配列内のすべての要素に対してこれらの手順を繰り返します。
配列要素をそれぞれのバケットに挿入する

配列要素をそれぞれのバケットに挿入する



ステップ 3: 各バケット内の要素を並べ替えます。この例では、クイックソート (または任意の安定した並べ替えアルゴリズム) を使用して、各バケット内の要素を並べ替えます。

各バケット内の要素を並べ替えます。

  • 安定した並べ替えアルゴリズム (バブル ソート、マージ ソートなど) を適用して、各バケット内の要素を並べ替えます。
  • 各バケット内の要素が並べ替えられました。
個々のバケットを並べ替える

個々のバケットを並べ替える

ステップ 4: 各バケットから要素を収集し、元の配列に戻します。

各バケットから要素を収集します。

  • 各バケットを順番に繰り返します。
  • バケットから元の配列に個々の要素を挿入します。
  • 要素がコピーされると、バケットから削除されます。
  • すべての要素が収集されるまで、すべてのバケットに対してこのプロセスを繰り返します。
結果の配列にバケットを昇順で挿入する

結果の配列にバケットを昇順で挿入する

ステップ5: 元の配列には、ソートされた要素が含まれています。

指定された入力に対してバケット ソートを使用してソートされた最終的な配列は [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94] です。

ソートされた配列を返す

ソートされた配列を返す

バケットソートアルゴリズムの実装:

以下はバケット ソートの実装です。

C++ 
#include  #include  using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& バケット) { for (int i = 1; i< bucket.size(); ++i) {  float key = bucket[i];  int j = i - 1;  while (j>= 0 && バケット[j]> キー) { バケット[j + 1] = バケット[j];  j--;  バケット[j + 1] = キー;  } } // バケット ソートを使用してサイズ n の arr[] をソートする関数 voidbucketSort(float arr[], int n) { // 1) n 個の空のバケット ベクトルを作成しますb[n];  // 2) 配列要素を異なるバケットに入れます for (int i = 0; i< n; i++) {  int bi = n * arr[i];  b[bi].push_back(arr[i]);  }  // 3) Sort individual buckets using insertion sort  for (int i = 0; i < n; i++) {  insertionSort(b[i]);  }  // 4) Concatenate all buckets into arr[]  int index = 0;  for (int i = 0; i < n; i++) {  for (int j = 0; j < b[i].size(); j++) {  arr[index++] = b[i][j];  }  } } // Driver program to test above function int main() {  float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};  int n = sizeof(arr) / sizeof(arr[0]);  bucketSort(arr, n);  cout << 'Sorted array is 
';  for (int i = 0; i < n; i++) {  cout << arr[i] << ' ';  }  return 0; }>
ジャワ 
import java.util.ArrayList; import java.util.List; public class Main {  // Insertion sort function to sort individual buckets  public static void insertionSort(Listバケット) { for (int i = 1; i< bucket.size(); ++i) {  float key = bucket.get(i);  int j = i - 1;  while (j>= 0 && バケット.get(j)> key) {バケット.set(j + 1, バケット.get(j));  j--;  バケット.set(j + 1, キー);  } } // バケットソートを使用してサイズ n の arr[] をソートする関数 public static voidbucketSort(float[] arr) { int n = arr.length;  // 1) n 個の空のバケットリストを作成します[] バケット = 新しい ArrayList[n];  for (int i = 0; i< n; i++) {  buckets[i] = new ArrayList();  }  // 2) Put array elements in different buckets  for (int i = 0; i < n; i++) {  int bi = (int) (n * arr[i]);  buckets[bi].add(arr[i]);  }  // 3) Sort individual buckets using insertion sort  for (int i = 0; i < n; i++) {  insertionSort(buckets[i]);  }  // 4) Concatenate all buckets into arr[]  int index = 0;  for (int i = 0; i < n; i++) {  for (int j = 0; j < buckets[i].size(); j++) {  arr[index++] = buckets[i].get(j);  }  }  }  // Driver program to test above function  public static void main(String[] args) {  float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};  bucketSort(arr);  System.out.println('Sorted array is:');  for (float num : arr) {  System.out.print(num + ' ');  }  } }>
パイソン 
def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 およびバケット[j]> キー: バケット[j + 1] = バケット[j] j -= 1 バケット[j + 1] = キー defbucket_sort(arr): n = len(arr) バケット = [[] for _ in range(n)] # 配列要素を異なるバケットに入れる for num in arr: bi = int(n * num)buckets[bi].append(num) # 挿入ソートを使用して個々のバケットを並べ替える for Bucket in Bucket: insert_sort (bucket) # すべてのバケットを arr[] に連結します。index = 0 forbucket inbuckets: for num in Bucket: arr[index] = numindex += 1 arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]bucket_sort (arr) print('ソートされた配列は:') print(' '.join(map(str, arr)))>>
C# 
using System; using System.Collections.Generic; class Program {  // Insertion sort function to sort individual buckets  static void InsertionSort(Listバケット) { for (int i = 1; i< bucket.Count; ++i)  {  float key = bucket[i];  int j = i - 1;  while (j>= 0 && バケット[j]> キー) { バケット[j + 1] = バケット[j];  j--;  バケット[j + 1] = キー;  } } // バケットソートを使用してサイズ n の arr[] をソートする関数 static void BucketSort(float[] arr) { int n = arr.Length;  // 1) n 個の空のバケットリストを作成します[] バケット = 新しいリスト[n];  for (int i = 0; i< n; i++)  {  buckets[i] = new List();  } // 2) 配列要素を異なるバケットに置きます (int i = 0; i< n; i++)  {  int bi = (int)(n * arr[i]);  buckets[bi].Add(arr[i]);  }  // 3) Sort individual buckets using insertion sort  for (int i = 0; i < n; i++)  {  InsertionSort(buckets[i]);  }  // 4) Concatenate all buckets into arr[]  int index = 0;  for (int i = 0; i < n; i++)  {  for (int j = 0; j < buckets[i].Count; j++)  {  arr[index++] = buckets[i][j];  }  }  }  // Driver program to test above function  static void Main(string[] args)  {  float[] arr = { 0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f };  BucketSort(arr);  Console.WriteLine('Sorted array is:');  foreach (float num in arr)  {  Console.Write(num + ' ');  }  } }>
JavaScript 
function insertionSort(bucket) {  for (let i = 1; i < bucket.length; ++i) {  let key = bucket[i];  let j = i - 1;  while (j>= 0 && バケット[j]> キー) { バケット[j + 1] = バケット[j];  j--;  バケット[j + 1] = キー;  関数bucketSort(arr) { let n = arr.length;  letbuckets = Array.from({length: n}, () => []);  // 配列要素を別のバケットに入れます (let i = 0; i< n; i++) {  let bi = Math.floor(n * arr[i]);  buckets[bi].push(arr[i]);  }  // Sort individual buckets using insertion sort  for (let i = 0; i < n; i++) {  insertionSort(buckets[i]);  }  // Concatenate all buckets into arr[]  let index = 0;  for (let i = 0; i < n; i++) {  for (let j = 0; j < buckets[i].length; j++) {  arr[index++] = buckets[i][j];  }  } } let arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]; bucketSort(arr); console.log('Sorted array is:'); console.log(arr.join(' '));>
出力 
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>

バケットソートアルゴリズムの複雑さの分析:

時間計算量: の上2）、

  • バケットへの挿入に O(1) 時間がかかると仮定すると、上記のアルゴリズムのステップ 1 と 2 には明らかに O(n) 時間がかかります。
  • O(1) は、バケットを表すリンク リストを使用すれば簡単に実現できます。
  • すべてのバケットに n 個の項目があるため、ステップ 4 にも O(n) 時間がかかります。
  • 分析する主なステップはステップ 3 です。すべての数値が一様に分布している場合、このステップにも平均で O(n) 時間がかかります。

補助スペース: O(n+k)