V tomto článku budeme diskutovať o algoritme triedenia počítania. Triedenie počítania je technika triedenia, ktorá je založená na kľúčoch medzi konkrétnymi rozsahmi. Pri kódovaní alebo technických pohovoroch pre softvérových inžinierov sú často kladené otázky na triediace algoritmy. Preto je dôležité diskutovať o téme.
Táto technika triedenia nevykonáva triedenie porovnávaním prvkov. Vykonáva triedenie počítaním objektov s odlišnými kľúčovými hodnotami, ako je hashovanie. Potom vykoná niekoľko aritmetických operácií na výpočet indexovej pozície každého objektu vo výstupnej sekvencii. Triedenie počítania sa nepoužíva ako všeobecný algoritmus triedenia.
Triedenie počítania je účinné, keď rozsah nie je väčší ako počet objektov, ktoré sa majú triediť. Môže sa použiť na triedenie záporných vstupných hodnôt.
Teraz sa pozrime na algoritmus triedenia počítania.
Proces Android acore sa stále zastavuje
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
Fungovanie algoritmu triedenia počítania
Teraz sa pozrime na fungovanie algoritmu triedenia počítania.
Aby sme pochopili fungovanie triediaceho algoritmu počítania, zoberme si nezoradené pole. Na príklade bude jednoduchšie pochopiť triedenie počítania.
Nech sú prvky poľa -
1. Nájdite maximálny prvok z daného poľa. Nechaj max byť maximálnym prvkom.
2. Teraz inicializujte pole dĺžky max + 1 so všetkými 0 prvkami. Toto pole sa použije na uloženie počtu prvkov v danom poli.
3. Teraz musíme uložiť počet každého prvku poľa na ich zodpovedajúcom indexe v poli počtu.
Počet prvku bude uložený ako - Predpokladajme, že prvok poľa '4' sa objavil dvakrát, takže počet prvku 4 je 2. Preto je 2 uložený na 4.thpozícia počítacieho poľa. Ak sa v poli nenachádza žiadny prvok, umiestnite 0, t.j. predpokladajme, že prvok „3“ nie je prítomný v poli, takže 0 bude uložená na 3rdpozíciu.
Teraz uložte kumulatívny súčet počítať prvky poľa. Pomôže umiestniť prvky na správny index zoradeného poľa.
Podobne kumulatívny počet poľa počtu je -
4. Teraz nájdite index každého prvku pôvodného poľa
Po umiestnení prvku na jeho miesto znížte jeho počet o jeden. Pred umiestnením prvku 2 bol jeho počet 2, ale po jeho umiestnení na správnu pozíciu je nový počet prvku 2 1.
java konštanta
Podobne po zoradení sú prvky poľa -
Teraz je pole úplne zoradené.
Počítanie zložitosti triedenia
Teraz sa pozrime na časovú zložitosť triedenia počítania v najlepšom prípade, priemernom prípade a v najhoršom prípade. Uvidíme aj priestorovú náročnosť počítania.
1. Časová zložitosť
| Prípad | Čas | Zložitosť |
|---|---|---|
| Najlepší prípad | O(n + k) | |
| Priemerný prípad | O(n + k) | |
| V najhoršom prípade | O(n + k) |
Vo všetkých vyššie uvedených prípadoch je časová zložitosť triedenia počítania rovnaká. Je to preto, že algoritmus prechádza n+k bez ohľadu na to, ako sú prvky umiestnené v poli.
java bool na reťazec
Triedenie počítania je lepšie ako techniky triedenia založené na porovnávaní, pretože pri triedení počítania neexistuje žiadne porovnanie medzi prvkami. Keď sú však celé čísla veľmi veľké, triedenie počítania je zlé, pretože je potrebné vytvoriť polia tejto veľkosti.
2. Zložitosť priestoru
| Vesmírna zložitosť | O (max.) |
| Stabilný | ÁNO |
- Priestorová zložitosť triedenia počítania je O(max). Čím väčší je rozsah prvkov, tým väčšia je zložitosť priestoru.
Implementácia triedenia počítania
Teraz sa pozrime na programy triedenia počítania v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu triedenia počítania v jazyku 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ýkon
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.
Tento článok nebol obmedzený len na algoritmus. Diskutovali sme aj o počítaní zložitosti triedenia, práci a implementácii v rôznych programovacích jazykoch.