In dit artikel bespreken we het telsoortalgoritme. Telsortering is een sorteertechniek die is gebaseerd op de sleutels tussen specifieke bereiken. In codeer- of technische interviews voor software-ingenieurs wordt veel gevraagd naar sorteeralgoritmen. Het is dus belangrijk om het onderwerp te bespreken.
Deze sorteertechniek voert geen sortering uit door elementen te vergelijken. Het sorteert door objecten te tellen met verschillende sleutelwaarden, zoals hashen. Daarna voert het enkele rekenkundige bewerkingen uit om de indexpositie van elk object in de uitvoerreeks te berekenen. Telsortering wordt niet gebruikt als sorteeralgoritme voor algemene doeleinden.
Telsortering is effectief als het bereik niet groter is dan het aantal te sorteren objecten. Het kan worden gebruikt om de negatieve invoerwaarden te sorteren.
Laten we nu eens kijken naar het algoritme voor het tellen van sorteringen.
Algoritme
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
Werking van telsoortalgoritme
Laten we nu eens kijken naar de werking van het teltype-algoritme.
Om de werking van het tellende sorteeralgoritme te begrijpen, nemen we een ongesorteerde array. Het zal gemakkelijker zijn om de telsoort te begrijpen aan de hand van een voorbeeld.
turbo c++ downloaden
Laat de elementen van array zijn -
1. Zoek het maximale element uit de gegeven array. Laten maximaal het maximale element zijn.
2. Initialiseer nu de array met lengte maximaal + 1 met alle 0 elementen. Deze array wordt gebruikt om het aantal elementen in de gegeven array op te slaan.
3. Nu moeten we de telling van elk array-element opslaan in de overeenkomstige index in de count-array.
De telling van een element wordt opgeslagen als - Stel dat array-element '4' twee keer voorkomt, dus de telling van element 4 is 2. Daarom wordt 2 opgeslagen op de 4epositie van de telarray. Als een element niet aanwezig is in de array, plaats dan 0, d.w.z. stel dat element '3' niet aanwezig is in de array, dus 0 wordt opgeslagen op 3rdpositie.
Sla nu de cumulatieve som op van graaf array-elementen. Het zal helpen om de elementen op de juiste index van de gesorteerde array te plaatsen.
Op dezelfde manier is de cumulatieve telling van de telreeks -
4. Zoek nu de index van elk element van de originele array
Nadat je het element op zijn plaats hebt geplaatst, verlaag je het aantal met één. Voordat element 2 werd geplaatst, was de telling 2, maar nadat deze op de juiste positie was geplaatst, is de nieuwe telling voor element 2 1.
Op dezelfde manier zijn de array-elementen na het sorteren -
Nu is de array volledig gesorteerd.
Sorteercomplexiteit tellen
Laten we nu eens kijken naar de tijdscomplexiteit van het tellen in het beste geval, het gemiddelde en het slechtste geval. We zullen ook de ruimtecomplexiteit van de telsoort zien.
1. Tijdcomplexiteit
| Geval | Tijd | Complexiteit |
|---|---|---|
| Beste geval | O(n + k) | |
| Gemiddeld geval | O(n + k) | |
| Het slechtste geval | O(n + k) |
In alle bovenstaande gevallen is de tijdscomplexiteit van het tellen hetzelfde. Dit komt omdat het algoritme doorgaat n+k keer, ongeacht hoe de elementen in de array zijn geplaatst.
Telsortering is beter dan de op vergelijkingen gebaseerde sorteertechnieken, omdat er geen vergelijking is tussen elementen bij telsortering. Maar als de gehele getallen erg groot zijn, is de telsoort slecht omdat er arrays van die grootte moeten worden gemaakt.
2. Ruimtecomplexiteit
| Ruimtecomplexiteit | O(max) |
| Stal | JA |
- De ruimtecomplexiteit van telsortering is O(max). Hoe groter het scala aan elementen, hoe groter de complexiteit van de ruimte.
Implementatie van telsortering
Laten we nu eens kijken naar de programma's voor het tellen van sorteringen in verschillende programmeertalen.
Programma: Schrijf een programma om telsortering in C-taal te implementeren.
#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;></=> Uitvoer
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.
Dit artikel beperkte zich niet alleen tot het algoritme. We hebben ook gesproken over het tellen van de sorteercomplexiteit, de werking en de implementatie in verschillende programmeertalen.