I den här artikeln kommer vi att diskutera algoritmen för räknesortering. Räknesortering är en sorteringsteknik som bygger på nycklarna mellan specifika intervall. I kodnings- eller tekniska intervjuer för mjukvaruingenjörer är sorteringsalgoritmer många frågade. Så det är viktigt att diskutera ämnet.
en miljon i siffror
Denna sorteringsteknik utför inte sortering genom att jämföra element. Den utför sortering genom att räkna objekt som har distinkta nyckelvärden som hash. Efter det utför den några aritmetiska operationer för att beräkna varje objekts indexposition i utdatasekvensen. Räknesortering används inte som en allmän sorteringsalgoritm.
Räkna sortering är effektivt när intervallet inte är större än antalet objekt som ska sorteras. Den kan användas för att sortera de negativa ingångsvärdena.
Låt oss nu se algoritmen för räkningssort.
Algoritm
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
Arbetar med räknesortsalgoritm
Låt oss nu se hur algoritmen för räkningssort fungerar.
För att förstå hur sorteringsalgoritmen fungerar, låt oss ta en osorterad array. Det blir lättare att förstå räknesorten via ett exempel.
Låt elementen i arrayen vara -
1. Hitta det maximala elementet från den givna arrayen. Låta max vara det maximala elementet.
2. Initiera nu längdmatrisen max + 1 har alla 0 element. Denna array kommer att användas för att lagra antalet element i den givna arrayen.
3. Nu måste vi lagra räkningen för varje arrayelement vid deras motsvarande index i count arrayen.
Antalet för ett element kommer att lagras som - Antag att arrayelementet '4' visas två gånger, så räkningen av element 4 är 2. Därför lagras 2 vid 4:anthpositionen för räknematrisen. Om något element inte finns i arrayen, placera 0, d.v.s. anta att element '3' inte finns i arrayen, så kommer 0 att lagras vid 3rdplacera.
Lagra nu den ackumulerade summan av räkna arrayelement. Det kommer att hjälpa till att placera elementen i rätt index för den sorterade arrayen.
På liknande sätt är det kumulativa antalet för räknematrisen -
4. Hitta nu indexet för varje element i den ursprungliga arrayen
Efter att ha placerat elementet på sin plats, minska dess antal med en. Innan element 2 placerades var dess räknevärde 2, men efter att det placerats i rätt position är det nya räknevärdet för element 2 1.
På liknande sätt, efter sortering, är arrayelementen -
Nu är arrayen helt sorterad.
Räkna sorts komplexitet
Låt oss nu se tidskomplexiteten för att räkna sortering i bästa fall, genomsnittligt fall och i värsta fall. Vi kommer också att se rymdkomplexiteten hos räknesorten.
1. Tidskomplexitet
| Fall | Tid | Komplexitet |
|---|---|---|
| Bästa fall | O(n + k) | |
| Genomsnittligt fall | O(n + k) | |
| Värsta fall | O(n + k) |
I alla ovanstående fall är tidskomplexiteten för att räkna sortering densamma. Detta beror på att algoritmen går igenom n+k gånger, oavsett hur elementen är placerade i arrayen.
Räknesortering är bättre än de jämförelsebaserade sorteringsteknikerna eftersom det inte finns någon jämförelse mellan element i räknesortering. Men när heltalen är mycket stora är räknesorteringen dålig eftersom arrayer av den storleken måste skapas.
2. Rymdkomplexitet
| Rymdkomplexitet | O(max) |
| Stabil | JA |
- Rymdkomplexiteten för räknesortering är O(max). Ju större utbud av element, desto större utrymmeskomplexitet.
Implementering av räknesort
Låt oss nu se räkningsprogrammen på olika programmeringsspråk.
Program: Skriv ett program för att implementera räknesortering 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;></=> Produktion
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.
Den här artikeln var inte bara begränsad till algoritmen. Vi har också diskuterat att räkna sorts komplexitet, arbete och implementering i olika programmeringsspråk.