logo

TechCodeview

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

この記事では、バケットソートアルゴリズムについて説明します。バケットソートのデータ項目はバケットの形式で分散されます。ソフトウェア エンジニアのコーディング面接や技術面接では、ソート アルゴリズムについてよく質問されます。したがって、そのテーマについて話し合うことが重要です。

バケット ソートは、要素をバケットと呼ばれる複数のグループに分ける並べ替えアルゴリズムです。バケット ソートの要素は、まずバケットと呼ばれるグループに均等に分割され、その後、他の並べ替えアルゴリズムによって並べ替えられます。その後、ソートされた方法で要素が収集されます。

バケットソートを実行する基本的な手順は次のとおりです。

  • まず、範囲を固定数のバケットに分割します。
  • 次に、すべての要素を適切なバケットに放り込みます。
  • その後、並べ替えアルゴリズムを適用して各バケットを個別に並べ替えます。
  • 最後に、ソートされたすべてのバケットを連結します。

バケットソートの利点は次のとおりです。

  • バケットソートにより数が減ります。比較の。
  • 要素が一様に分布しているため、漸近的に高速になります。

バケットソートの制限事項は次のとおりです。

  • これは安定した並べ替えアルゴリズムである場合もあれば、そうでない場合もあります。
  • 大きな配列がある場合、コストが増加するため役に立ちません。
  • バケットを並べ替えるには追加のスペースが必要となるため、これはインプレース並べ替えアルゴリズムではありません。

バケットソートの最良および平均的な複雑さは次のとおりです。 O(n + k) 、バケット ソートの最悪の場合の複雑さは次のとおりです。 の上2) 、 どこ n 項目数です。

バケットソートが一般的に使用されます -

  • 浮動小数点値を使用します。
  • 入力が範囲全体に均一に分布している場合。

バケットソートを実行するための基本的な考え方は次のようになります。

 bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort

それでは、バケットソートのアルゴリズムを見てみましょう。

アルゴリズム

 Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End

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

バケット ソート アルゴリズムは、スキャッター ギャザー アプローチによって理解できます。ここでは、指定された要素が最初にバケットに分散されます。分散後、各バケット内の要素は、安定した並べ替えアルゴリズムを使用して並べ替えられます。最後に、ソートされた要素が順番に集められます。

バケットソートのプロセスを理解するために、ソートされていない配列を取り上げてみましょう。バケットソートについては、例を参照すると理解しやすくなります。

配列の要素を次のようにします -

バケットソート

次に、0 ～ 25 の範囲のバケットを作成します。バケットの範囲は 0 ～ 5、5 ～ 10、10 ～ 15、15 ～ 20、20 ～ 25 です。要素はバケット範囲に従ってバケットに挿入されます。アイテムの値が 16 であると仮定すると、アイテムは 15 ～ 20 の範囲でバケットに挿入されます。同様に、配列の各項目もそれに応じて挿入されます。

この段階は次のように知られています。 配列要素の分散 。

バケットソート

今、 選別 各バケットを個別に。各バケットの要素は、安定した並べ替えアルゴリズムのいずれかを使用して並べ替えることができます。

バケットソート

やっと、 集める 各バケットの要素を順番にソート

バケットソート

これで、配列が完全にソートされました。

バケットソートの複雑さ

ここで、最良のケース、平均的なケース、最悪のケースにおけるバケット ソートの時間計算量を見てみましょう。バケット ソートの空間の複雑さも見ていきます。

1. 時間計算量

場合 時間 複雑
最良の場合 O(n + k)
平均的なケース O(n + k)
最悪の場合 の上2)
    最高のケースの複雑さ -これは、並べ替えが必要ない場合、つまり配列がすでに並べ替えられている場合に発生します。バケットソートでは、要素がバケット内に均一に分散されている場合に最適な状況が発生します。要素がバケット内ですでにソートされている場合、複雑さは改善されます。
    挿入ソートを使用してバケット要素をソートする場合、全体の複雑さは線形、つまり O(n + k) になります。ここで、O(n) はバケットの作成に使用され、O(k) はバケット要素のソートに使用されます。最良の場合でも線形時間計算量のアルゴリズムを使用します。
    バケットソートの最良の場合の時間計算量は次のとおりです。 O(n + k) 。平均的なケースの複雑さ -この問題は、配列要素の順序が正しく昇順または降順ではなく、ごちゃ混ぜになっている場合に発生します。バケット ソートは、要素が均一に分散されている場合でも、線形時間で実行されます。バケットソートの平均ケース時間複雑さは次のとおりです。 O(n + K) 。最悪の場合の複雑さ -バケット ソートでは、要素が配列内で近い範囲にある場合に最悪のケースが発生します。そのため、要素を同じバケットに配置する必要があります。したがって、一部のバケットには他のバケットよりも多くの要素があります。
    要素の順序が逆の場合、複雑さはさらに悪化します。
    バケットソートの最悪の場合の時間計算量は次のとおりです。 の上2) 。

2. 空間の複雑さ

空間の複雑さ O(n*k)
安定した はい
  • バケット ソートの空間計算量は O(n*k) です。

バケットソートの実装

ここで、さまざまなプログラミング言語でのバケット ソートのプログラムを見てみましょう。

プログラム： C言語でバケットソートを実装するプログラムを書きます。

 #include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are - 
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are - 
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are - 
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are - 
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>