I denne artikel vil vi diskutere optællingssorteringsalgoritmen. Tællesortering er en sorteringsteknik, der er baseret på nøglerne mellem specifikke områder. I kodnings- eller tekniske interviews for softwareingeniører er der mange spørgsmål om sorteringsalgoritmer. Så det er vigtigt at diskutere emnet.
Denne sorteringsteknik udfører ikke sortering ved at sammenligne elementer. Den udfører sortering ved at tælle objekter med forskellige nøgleværdier som hashing. Derefter udfører den nogle aritmetiske operationer for at beregne hvert objekts indeksposition i outputsekvensen. Tællesortering bruges ikke som en generel sorteringsalgoritme.
polymorfi i java
At tælle sortering er effektiv, når rækkevidden ikke er større end antallet af objekter, der skal sorteres. Den kan bruges til at sortere de negative inputværdier.
Lad os nu se algoritmen for optællingssortering.
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
Arbejde med at tælle sorteringsalgoritme
Lad os nu se, hvordan tællesortsalgoritmen fungerer.
For at forstå, hvordan tællesorteringsalgoritmen fungerer, lad os tage en usorteret matrix. Det bliver lettere at forstå optællingssorteringen via et eksempel.
Lad elementerne i array være -
1. Find det maksimale element fra det givne array. Lade max være det maksimale element.
2. Nu initialiser række af længde max + 1 med alle 0 elementer. Dette array vil blive brugt til at gemme antallet af elementer i det givne array.
3. Nu skal vi gemme tællingen af hvert array-element ved deres tilsvarende indeks i count-arrayet.
Antallet af et element vil blive lagret som - Antag, at array-elementet '4' vises to gange, så optællingen af element 4 er 2. Derfor er 2 gemt ved 4'erenthtællearrayets position. Hvis et element ikke er til stede i arrayet, placer 0, dvs. antag at element '3' ikke er til stede i arrayet, så 0 vil blive gemt ved 3rdposition.
bash for loop 1 til 10
Gem nu den kumulative sum af tælle array elementer. Det vil hjælpe med at placere elementerne på det korrekte indeks for det sorterede array.
På samme måde er det kumulative antal af tællearrayet -
4. Find nu indekset for hvert element i det originale array
Efter at have placeret elementet på sin plads, skal du reducere dets antal med én. Inden element 2 blev placeret, var dets antal 2, men efter at have placeret det i dens korrekte position, er den nye optælling for element 2 1.
På samme måde, efter sortering, er array-elementerne -
Nu er arrayet helt sorteret.
hvor mange frugter er der
Tælle sorterings kompleksitet
Lad os nu se tidskompleksiteten ved at tælle sortering i bedste tilfælde, gennemsnitligt tilfælde og i værste tilfælde. Vi vil også se rumkompleksiteten af optællingssorten.
1. Tidskompleksitet
| Sag | Tid | Kompleksitet |
|---|---|---|
| Bedste sag | O(n + k) | |
| Gennemsnitlig tilfælde | O(n + k) | |
| Worst Case | O(n + k) |
I alle ovenstående tilfælde er tidskompleksiteten af optællingssortering den samme. Dette skyldes, at algoritmen går igennem n+k gange, uanset hvordan elementerne er placeret i arrayet.
maskinskrift for hver
Optællingssortering er bedre end de sammenligningsbaserede sorteringsteknikker, fordi der ikke er nogen sammenligning mellem elementer i optællingssortering. Men når heltalene er meget store, er optællingssorteringen dårlig, fordi arrays af den størrelse skal oprettes.
2. Rumkompleksitet
| Rumkompleksitet | O(max) |
| Stabil | JA |
- Rumkompleksiteten ved at tælle sortering er O(max). Jo større udvalg af elementer, desto større er rummets kompleksitet.
Implementering af tællesort
Lad os nu se tælleprogrammerne på forskellige programmeringssprog.
Program: Skriv et program til at implementere tællesort i C-sprog.
#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;></=> Produktion
Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig.
Denne artikel var ikke kun begrænset til algoritmen. Vi har også diskuteret tælle sorterings kompleksitet, arbejde og implementering i forskellige programmeringssprog.