logo

TechCodeview

基数ソートアルゴリズム

この記事では、基数ソート アルゴリズムについて説明します。基数ソートは、整数に使用される線形ソート アルゴリズムです。基数ソートでは、最下位桁から最上位桁に向かって桁ごとにソートが実行されます。

基数ソートのプロセスは、アルファベット順に生徒の名前をソートするのと同様に機能します。この場合、英語の 26 個のアルファベットにより 26 個の基数が形成されます。最初のパスでは、生徒の名前は名前の最初の文字の昇順に従ってグループ化されます。その後、2 パス目で名前の 2 文字目の昇順にグループ化されます。そして、ソートされたリストが見つかるまでこのプロセスが続きます。

州のリスト

さて、基数ソートのアルゴリズムを見てみましょう。

アルゴリズム

 radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -> 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place

基数ソートアルゴリズムの仕組み

ここで、基数ソート アルゴリズムの仕組みを見てみましょう。

基数ソートのソートに使用される手順は次のとおりです。

  • まず、最大の要素を見つける必要があります (次のようにします) 最大 ) 指定された配列から。仮定する 'バツ' の桁数になります 最大 。の 'バツ' すべての要素の重要な場所を通過する必要があるため、計算されます。
  • その後、重要な場所を 1 つずつ見ていきます。ここでは、安定した並べ替えアルゴリズムを使用して、各有効桁の数字を並べ替える必要があります。

次に、例を使用して基数ソートの仕組みを詳しく見てみましょう。これをより明確に理解するために、ソートされていない配列を取得し、基数ソートを使用してソートしてみます。説明がより明確かつ簡単になります。

基数ソートアルゴリズム

指定された配列の最大の要素は次のとおりです。 736 持っている 3 その中の数字。したがって、ループは最大 3 回実行されます (つまり、 百の位 ）。つまり、配列をソートするには 3 つのパスが必要です。

ここで、まず単位の位の桁に基づいて要素を並べ替えます (つまり、 x = 0 ）。ここでは、カウントソートアルゴリズムを使用して要素をソートしています。

パス 1:

最初のパスでは、リストは 0 の位の数字に基づいて並べ替えられます。

基数ソートアルゴリズム

最初のパスの後、配列要素は次のようになります -

基数ソートアルゴリズム

パス 2:

このパスでは、リストは次の有効数字 (つまり 10 の数字) に基づいて並べ替えられます。番目場所）。

基数ソートアルゴリズム

2 回目のパスの後、配列要素は次のようになります -

基数ソートアルゴリズム

パス 3:

このパスでは、リストは次の有効数字 (つまり 100 の数字) に基づいて並べ替えられます。番目場所）。

基数ソートアルゴリズム

3 回目のパスの後、配列要素は次のようになります -

基数ソートアルゴリズム

これで、配列が昇順に並べ替えられました。

基数ソートの複雑さ

ここで、基数ソートの時間計算量を最良の場合、平均的な場合、最悪の場合で見てみましょう。基数ソートの空間の複雑さも見ていきます。

1. 時間計算量

場合 時間計算量
最良の場合 Ω(n+k)
平均的なケース θ(nk)
最悪の場合 O(nk)
    最高のケースの複雑さ -これは、並べ替えが必要ない場合、つまり配列がすでに並べ替えられている場合に発生します。基数ソートの最良の場合の時間計算量は次のとおりです。 Ω(n+k) 。平均的なケースの複雑さ -この問題は、配列要素の順序が正しく昇順または降順ではなく、ごちゃ混ぜになっている場合に発生します。基数ソートの平均ケース時間計算量は次のとおりです。 θ(nk) 。最悪の場合の複雑さ -これは、配列要素を逆順に並べ替える必要がある場合に発生します。つまり、配列要素を昇順に並べ替える必要があるが、その要素は降順になっているとします。基数ソートの最悪の場合の時間計算量は次のとおりです。 O(nk) 。

基数ソートは、比較ソート アルゴリズムよりも優れた非比較ソート アルゴリズムです。線形時間計算量は、計算量 O(n logn) の比較アルゴリズムよりも優れています。

配列Javaに追加

2. 空間の複雑さ

空間の複雑さ O(n + k)
安定した はい
  • 基数ソートの空間計算量は O(n + k) です。

基数ソートの実装

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

プログラム： C言語で基数ソートを実装するプログラムを作成します。

 #include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarray(a,n); radixsort(a, n); cout<<'

after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); console.write('

after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are - 
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('

after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>