この記事では、カウントソートアルゴリズムについて説明します。カウントソートは、特定の範囲間のキーに基づくソート手法です。ソフトウェア エンジニアのコーディング面接や技術面接では、ソート アルゴリズムについてよく質問されます。したがって、そのテーマについて話し合うことが重要です。
この並べ替え手法では、要素の比較による並べ替えは実行されません。ハッシュのように個別のキー値を持つオブジェクトをカウントすることでソートを実行します。その後、いくつかの算術演算を実行して、出力シーケンス内の各オブジェクトのインデックス位置を計算します。カウンティング ソートは、汎用のソート アルゴリズムとしては使用されません。
カウントソートは、範囲がソート対象のオブジェクトの数を超えない場合に有効です。負の入力値を並べ替えるのに使用できます。
文字列配列c
それでは、カウントソートのアルゴリズムを見てみましょう。
アルゴリズム
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
カウンティングソートアルゴリズムの仕組み
ここで、カウンティングソートアルゴリズムの仕組みを見てみましょう。
カウントソートアルゴリズムの動作を理解するために、ソートされていない配列を取り上げてみましょう。例を使用すると、カウントソートを理解しやすくなります。
配列の要素を次のようにします -
1. 指定された配列から最大の要素を見つけます。させて 最大 が最大の要素となります。
2. ここで、長さの配列を初期化します 最大 + 1 すべての要素が 0 です。この配列は、指定された配列内の要素の数を保存するために使用されます。
3. ここで、各配列要素のカウントを count 配列の対応するインデックスに保存する必要があります。
要素のカウントは次のように格納されます。配列要素 '4' が 2 回出現すると仮定すると、要素 4 のカウントは 2 になります。したがって、2 は 4 の位置に格納されます。番目count 配列の位置。配列内に要素が存在しない場合は、0 を配置します。つまり、要素 '3' が配列内に存在しないと仮定すると、0 は 3 に格納されます。rd位置。
文字列の長さJava
ここで、累積和を保存します カウント 配列要素。ソートされた配列の正しいインデックスに要素を配置すると役立ちます。
同様に、count 配列の累積カウントは -
4. ここで、元の配列の各要素のインデックスを見つけます。
要素をその場所に配置した後、そのカウントを 1 つ減らします。要素 2 を配置する前はそのカウントは 2 でしたが、正しい位置に配置した後は、要素 2 の新しいカウントは 1 になります。
同様に、並べ替え後の配列要素は次のようになります。
これで、配列が完全にソートされました。
ソートの複雑さをカウントする
ここで、最良のケース、平均的なケース、最悪のケースにおけるカウンティングソートの時間計算量を見てみましょう。また、カウンティングソートの空間の複雑さも見ていきます。
文字列の比較C#
1. 時間計算量
| 場合 | 時間 | 複雑 |
|---|---|---|
| 最良の場合 | O(n + k) | |
| 平均的なケース | O(n + k) | |
| 最悪の場合 | O(n + k) |
上記のすべてのケースにおいて、ソートのカウントにかかる時間の複雑さは同じです。これはアルゴリズムが通過するためです n+k 要素が配列内にどのように配置されているかに関係なく、
カウントソートでは要素間の比較がないため、カウントソートは比較ベースのソート手法よりも優れています。ただし、整数が非常に大きい場合、そのサイズの配列を作成する必要があるため、カウントの並べ替えは適切ではありません。
2. 空間の複雑さ
| 空間の複雑さ | O(最大) |
| 安定した | はい |
- カウンティングソートの空間複雑さは O(max) です。要素の範囲が広いほど、空間の複雑さは大きくなります。
カウンティングソートの実装
ここで、さまざまなプログラミング言語でのカウンティングソートのプログラムを見てみましょう。
トーチの取り付け
プログラム： 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; 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/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; 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/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); 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/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that'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. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> 出力
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。
この記事はアルゴリズムだけに限定されたものではありません。また、ソートの複雑さのカウント、動作、さまざまなプログラミング言語での実装についても説明しました。