V tem članku bomo razpravljali o algoritmu razvrščanja štetja. Razvrščanje s štetjem je tehnika razvrščanja, ki temelji na ključih med določenimi obsegi. V kodirnih ali tehničnih intervjujih za programske inženirje se veliko sprašuje o algoritmih razvrščanja. Zato je pomembno razpravljati o temi.
Ta tehnika razvrščanja ne izvaja razvrščanja s primerjavo elementov. Izvaja razvrščanje s štetjem predmetov, ki imajo različne ključne vrednosti, kot je zgoščevanje. Po tem izvede nekaj aritmetičnih operacij za izračun položaja indeksa vsakega predmeta v izhodnem zaporedju. Razvrščanje s štetjem se ne uporablja kot splošni algoritem za razvrščanje.
Razvrščanje s štetjem je učinkovito, če obseg ni večji od števila predmetov, ki jih je treba razvrstiti. Uporablja se lahko za razvrščanje negativnih vhodnih vrednosti.
Zdaj pa si oglejmo algoritem razvrščanja štetja.
primerek v Javi
Algoritem
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
Delovanje algoritma za razvrščanje štetja
Zdaj pa poglejmo delovanje algoritma za razvrščanje s štetjem.
Da bi razumeli delovanje algoritma razvrščanja s štetjem, vzemimo nerazvrščeno matriko. Razvrščanje štetja bo lažje razumeti na primeru.
Naj so elementi matrike -
1. Poiščite največji element iz podane matrike. Pustiti maks biti največji element.
2. Zdaj inicializirajte niz dolžine največ + 1 ki ima vseh 0 elementov. Ta matrika bo uporabljena za shranjevanje števila elementov v dani matriki.
3. Sedaj moramo shraniti štetje vsakega elementa matrike na njihov ustrezni indeks v matriki štetja.
Število elementa bo shranjeno kot - Recimo, da se element matrike '4' pojavi dvakrat, tako da je število elementa 4 2. Zato je 2 shranjen na 4thpoložaj matrike štetja. Če kateri koli element ni prisoten v matriki, postavite 0, tj. predpostavimo, da element '3' ni prisoten v matriki, torej bo 0 shranjena na 3rdpoložaj.
Zdaj shranite kumulativno vsoto štetje elementi niza. To bo pomagalo postaviti elemente na pravi indeks razvrščene matrike.
Podobno je kumulativno število matrike štetja -
4. Zdaj poiščite indeks vsakega elementa izvirne matrike
Ko postavite element na svoje mesto, zmanjšajte njegovo število za eno. Pred namestitvijo elementa 2 je bilo njegovo število 2, po postavitvi na pravilno mesto pa je novo število za element 2 1.
Podobno so po razvrščanju elementi matrike -
Sedaj je niz popolnoma urejen.
Štetje zapletenosti razvrščanja
Zdaj pa poglejmo časovno zahtevnost razvrščanja štetja v najboljšem primeru, povprečnem primeru in v najslabšem primeru. Videli bomo tudi prostorsko zapletenost vrste štetja.
1. Časovna zapletenost
| Ovitek | Čas | Kompleksnost |
|---|---|---|
| Najboljši primer | O(n + k) | |
| Povprečen primer | O(n + k) | |
| V najslabšem primeru | O(n + k) |
V vseh zgornjih primerih je časovna zahtevnost razvrščanja štetja enaka. To je zato, ker gre algoritem skozi n+k krat, ne glede na to, kako so elementi postavljeni v matriko.
Razvrščanje s štetjem je boljše od tehnik razvrščanja na podlagi primerjave, ker pri razvrščanju s štetjem ni primerjave med elementi. Ko pa so cela števila zelo velika, je razvrščanje s štetjem slabo, ker je treba ustvariti nize te velikosti.
2. Kompleksnost prostora
| Kompleksnost prostora | O (maks.) |
| Stabilen | DA |
- Prostorska kompleksnost razvrščanja s štetjem je O(max). Večji kot je nabor elementov, večja je kompleksnost prostora.
Izvedba razvrščanja štetja
Zdaj pa si oglejmo programe za razvrščanje štetja v različnih programskih jezikih.
Program: Napišite program za izvajanje razvrščanja s štetjem v jeziku 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;></=> Izhod
javascript window.open
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.
Ta članek ni bil omejen le na algoritem. Razpravljali smo tudi o štetju kompleksnosti razvrščanja, delovanju in implementaciji v različnih programskih jezikih.