Tässä artikkelissa käsittelemme laskentalajittelualgoritmia. Laskentalajittelu on lajittelutekniikka, joka perustuu tiettyjen alueiden välisiin avaimiin. Ohjelmistoinsinöörien koodaus- tai teknisissä haastatteluissa lajittelualgoritmeja kysytään laajalti. Joten on tärkeää keskustella aiheesta.
Tämä lajittelutekniikka ei suorita lajittelua elementtejä vertailemalla. Se suorittaa lajittelun laskemalla objektit, joilla on erilliset avainarvot, kuten hajautus. Sen jälkeen se suorittaa joitain aritmeettisia operaatioita laskeakseen kunkin objektin indeksipaikan tulossekvenssissä. Laskevaa lajittelua ei käytetä yleiskäyttöisenä lajittelualgoritmina.
Laskennan lajittelu on tehokasta, kun alue ei ole suurempi kuin lajitettavien kohteiden lukumäärä. Sitä voidaan käyttää negatiivisten tuloarvojen lajitteluun.
Katsotaanpa nyt laskenta-lajittelun algoritmia.
Algoritmi
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
Laskentalajittelualgoritmin työskentely
Katsotaanpa nyt laskentalajittelualgoritmin toimintaa.
Ymmärtääksemme laskenta-lajittelualgoritmin toiminnan, otetaan lajittelematon matriisi. Laskentalajittelu on helpompi ymmärtää esimerkin avulla.
Olkoon taulukon elementit -
1. Etsi annetusta taulukosta suurin elementti. Antaa max olla suurin elementti.
2. Alusta nyt pituinen joukko max + 1 jossa on kaikki 0 elementtiä. Tätä taulukkoa käytetään tallentamaan tietyn taulukon elementtien lukumäärä.
3. Nyt meidän on tallennettava jokaisen taulukon elementin lukumäärä niiden vastaavaan indeksiin count-taulukossa.
ankita dave
Elementin määrä tallennetaan muodossa - Oletetaan, että taulukon elementti '4' esiintyy kaksi kertaa, joten elementin 4 määrä on 2. Näin ollen 2 tallennetaan kohtaan 4.thlaskentataulukon sijainti. Jos jokin elementti ei ole taulukossa, aseta 0, eli oletetaan, että elementtiä '3' ei ole taulukossa, joten 0 tallennetaan 3:een.rdasema.
Tallenna nyt kumulatiivinen summa Kreivi taulukon elementtejä. Se auttaa sijoittamaan elementit lajitellun taulukon oikeaan indeksiin.
Samoin count-taulukon kumulatiivinen määrä on -
4. Etsi nyt alkuperäisen taulukon kunkin elementin indeksi
Kun olet asettanut elementin paikoilleen, vähennä sen määrää yhdellä. Ennen elementin 2 sijoittamista sen luku oli 2, mutta kun se on asetettu oikeaan paikkaan, elementin 2 uusi luku on 1.
Vastaavasti lajittelun jälkeen taulukon elementit ovat -
Nyt matriisi on täysin lajiteltu.
Lajittelun monimutkaisuuden laskeminen
Katsotaan nyt laskentalajittelun aika monimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös laskentalajin avaruuden monimutkaisuuden.
1. Aika monimutkaisuus
| Asia | Aika | Monimutkaisuus |
|---|---|---|
| Paras tapaus | O(n + k) | |
| Keskimääräinen tapaus | O(n + k) | |
| Pahimmassa tapauksessa | O(n + k) |
Kaikissa yllä olevissa tapauksissa laskennan lajittelun aikamonimutkaisuus on sama. Tämä johtuu siitä, että algoritmi menee läpi n+k kertaa riippumatta siitä, miten elementit on sijoitettu taulukkoon.
Laskentalajittelu on parempi kuin vertailupohjaiset lajittelutekniikat, koska laskentalajittelussa ei ole vertailua elementtien välillä. Mutta kun kokonaisluvut ovat erittäin suuria, laskennan lajittelu on huono, koska on luotava tämän kokoisia taulukoita.
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O (max) |
| Vakaa | JOO |
- Laskentalajittelun tilamonimutkaisuus on O(max). Mitä suurempi elementtien valikoima, sitä suurempi on tilan monimutkaisuus.
Laskentalajittelun toteutus
Katsotaanpa nyt laskentaohjelmien lajittelua eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma laskennan lajittelun toteuttamiseksi C-kielellä.
#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;></=> Lähtö
vastaava merkkijono javassa
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.
Tämä artikkeli ei rajoittunut vain algoritmiin. Olemme myös keskustelleet laskennan lajittelun monimutkaisuudesta, toiminnasta ja toteutuksesta eri ohjelmointikielillä.