I denne artikkelen vil vi diskutere tellesorteringsalgoritmen. Tellesortering er en sorteringsteknikk som er basert på nøklene mellom spesifikke områder. I koding eller tekniske intervjuer for programvareingeniører er det mye spørsmål om sorteringsalgoritmer. Så det er viktig å diskutere temaet.
Denne sorteringsteknikken utfører ikke sortering ved å sammenligne elementer. Den utfører sortering ved å telle objekter med distinkte nøkkelverdier som hashing. Etter det utfører den noen aritmetiske operasjoner for å beregne hvert objekts indeksposisjon i utdatasekvensen. Tellesortering brukes ikke som en generell sorteringsalgoritme.
polymorfisme i java
Tellesortering er effektiv når rekkevidden ikke er større enn antall objekter som skal sorteres. Den kan brukes til å sortere de negative inngangsverdiene.
La oss nå se algoritmen for tellesortering.
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
Arbeid med tellesortalgoritme
La oss nå se hvordan tellesortalgoritmen fungerer.
For å forstå hvordan tellesorteringsalgoritmen fungerer, la oss ta en usortert matrise. Det vil være lettere å forstå tellesorten via et eksempel.
La elementene i array være -
1. Finn det maksimale elementet fra den gitte matrisen. La maks være det maksimale elementet.
2. Initialiser nå array of length maks + 1 har alle 0 elementer. Denne matrisen vil bli brukt til å lagre tellingen av elementene i den gitte matrisen.
3. Nå må vi lagre tellingen til hvert array-element ved deres tilsvarende indeks i count-arrayet.
Antallet av et element vil bli lagret som - Anta at array-elementet '4' vises to ganger, så antallet av element 4 er 2. Derfor er 2 lagret ved 4-enthposisjonen til tellematrisen. Hvis et element ikke er til stede i matrisen, plasser 0, dvs. anta at element '3' ikke er til stede i matrisen, så vil 0 bli lagret på 3rdposisjon.
bash for loop 1 til 10
Lagre nå den kumulative summen av telle array-elementer. Det vil hjelpe å plassere elementene på riktig indeks for den sorterte matrisen.
På samme måte er det kumulative antallet av tellematrisen -
4. Finn nå indeksen til hvert element i den opprinnelige matrisen
Etter å ha plassert elementet på plass, reduser antallet med én. Før element 2 ble plassert var tellingen 2, men etter å ha plassert den i riktig posisjon, er den nye tellingen for element 2 1.
På samme måte, etter sortering, er matriseelementene -
Nå er matrisen fullstendig sortert.
pyspark veiledning
Telle sorterings kompleksitet
La oss nå se tidskompleksiteten ved å telle sortering i beste tilfelle, gjennomsnittlig tilfelle og i verste fall. Vi vil også se plasskompleksiteten til tellesorten.
1. Tidskompleksitet
| Sak | Tid | Kompleksitet |
|---|---|---|
| Beste sak | O(n + k) | |
| Gjennomsnittlig sak | O(n + k) | |
| Worst Case | O(n + k) |
I alle ovennevnte tilfeller er tidskompleksiteten for tellesortering den samme. Dette er fordi algoritmen går gjennom n+k ganger, uavhengig av hvordan elementene er plassert i matrisen.
mia khalifa alder
Tellesortering er bedre enn de sammenligningsbaserte sorteringsteknikkene fordi det ikke er noen sammenligning mellom elementer i tellesortering. Men når heltallene er veldig store, er tellesorteringen dårlig fordi matriser av den størrelsen må opprettes.
2. Romkompleksitet
| Plass kompleksitet | O(maks) |
| Stabil | JA |
- Romkompleksiteten til å telle sortering er O(maks). Jo større spekter av elementer, desto større plasskompleksitet.
Gjennomføring av tellesort
La oss nå se tellingsprogrammene på forskjellige programmeringsspråk.
Program: Skriv et program for å implementere tellesortering i C-språk.
#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;></=> Produksjon
Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.
Denne artikkelen var ikke bare begrenset til algoritmen. Vi har også diskutert telling av sorteringskompleksitet, arbeid og implementering i forskjellige programmeringsspråk.