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

Paras tapauksen monimutkaisuus -Se tapahtuu, kun lajittelua ei vaadita, eli matriisi on jo lajiteltu. Laskentalajittelun paras tapaus aika monimutkaisuus on O(n + k) .Keskimääräinen tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit ovat sekaisin järjestyksessä, joka ei ole oikein nouseva eikä oikein laskeva. Laskentalajittelun tapausten keskimääräinen aika monimutkaisuus on O(n + k) .Pahimman tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit on lajiteltava käänteisessä järjestyksessä. Tämä tarkoittaa, että sinun on lajiteltava taulukon elementit nousevaan järjestykseen, mutta sen elementit ovat laskevassa järjestyksessä. Laskennan lajittelun pahin aika monimutkaisuus on 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

• 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>&apos;; printArray($a, $n); countSort($a,$n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </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&apos;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ä.