V tomto článku se budeme zabývat algoritmem řazení počítání. Počítání třídění je technika třídění, která je založena na klíčích mezi konkrétními rozsahy. Při kódování nebo technických pohovorech pro softwarové inženýry jsou často kladeny dotazy na třídicí algoritmy. Je tedy důležité o tématu diskutovat.
Tato technika třídění neprovádí třídění porovnáváním prvků. Provádí třídění počítáním objektů, které mají odlišné klíčové hodnoty, jako je hash. Poté provede některé aritmetické operace pro výpočet pozice indexu každého objektu ve výstupní sekvenci. Počítání řazení se nepoužívá jako obecný třídicí algoritmus.
Počítání třídění je účinné, když rozsah není větší než počet objektů, které mají být seřazeny. Lze jej použít k třídění záporných vstupních hodnot.
Nyní se podívejme na algoritmus řazení.
Algoritmus
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
Fungování algoritmu řazení počítání
Nyní se podívejme, jak funguje algoritmus řazení počítání.
Abychom porozuměli fungování třídícího algoritmu počítání, vezměme si netříděné pole. Uspořádání počítání bude snazší pochopit na příkladu.
Nechť prvky pole jsou -
1. Najděte maximální prvek z daného pole. Nechat max být maximálním prvkem.
2. Nyní inicializujte pole délky max + 1 mající všech 0 prvků. Toto pole bude použito k uložení počtu prvků v daném poli.
3. Nyní musíme uložit počet každého prvku pole na jejich odpovídající index v poli count.
Počet prvku bude uložen jako - Předpokládejme, že prvek pole '4' se objevil dvakrát, takže počet prvku 4 je 2. Proto je 2 uloženo na 4.čtpozice pole počtu. Pokud v poli není přítomen žádný prvek, umístěte 0, tj. předpokládejme, že prvek „3“ není v poli přítomen, takže 0 bude uložena na 3rdpozice.
Nyní uložte kumulativní součet počet prvky pole. Pomůže umístit prvky na správný index setříděného pole.
Podobně kumulativní počet pole počtu je -
4. Nyní najděte index každého prvku původního pole
Po umístění prvku na jeho místo snižte jeho počet o jednu. Před umístěním prvku 2 byl jeho počet 2, ale po umístění na správné místo je nový počet prvku 2 1.
Podobně po seřazení jsou prvky pole -
Nyní je pole kompletně seřazeno.
Počítání složitosti řazení
Nyní se podívejme na časovou složitost řazení počítání v nejlepším případě, průměrném případě a v nejhorším případě. Uvidíme také prostorovou složitost počítání.
1. Časová složitost
| Pouzdro | Čas | Složitost |
|---|---|---|
| Nejlepší případ | O(n + k) | |
| Průměrný případ | O(n + k) | |
| Nejhorší případ | O(n + k) |
Ve všech výše uvedených případech je časová složitost řazení počítání stejná. Je to proto, že algoritmus prochází n+k časy, bez ohledu na to, jak jsou prvky umístěny v poli.
Počítání třídění je lepší než techniky třídění založené na porovnávání, protože při třídění počítání neexistuje žádné srovnání mezi prvky. Ale když jsou celá čísla velmi velká, je řazení počítání špatné, protože pole této velikosti musí být vytvořena.
2. Prostorová složitost
| Vesmírná složitost | O (max.) |
| Stabilní | ANO |
- Prostorová složitost počítání je O(max). Čím větší je rozsah prvků, tím větší je prostorová složitost.
Implementace počítacího třídění
Nyní se podívejme na programy řazení počítání v různých programovacích jazycích.
přidávání řetězců java
Program: Napište program pro implementaci třídění počítání v jazyce 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;></=> Výstup
Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.
Tento článek nebyl omezen pouze na algoritmus. Také jsme diskutovali o počítání složitosti řazení, práci a implementaci v různých programovacích jazycích.