Šiame straipsnyje aptarsime skaičiavimo rūšiavimo algoritmą. Skaičiavimo rūšiavimas yra rūšiavimo metodas, pagrįstas raktais tarp konkrečių diapazonų. Kodavimo ar techninių pokalbių programinės įrangos inžinieriams metu plačiai klausiama rūšiavimo algoritmų. Taigi, svarbu aptarti temą.
Ši rūšiavimo technika neatlieka rūšiavimo lyginant elementus. Ji atlieka rūšiavimą skaičiuodama objektus, turinčius skirtingas pagrindines reikšmes, pvz., maišą. Po to jis atlieka kai kurias aritmetines operacijas, kad apskaičiuotų kiekvieno objekto indekso padėtį išvesties sekoje. Skaičiavimo rūšiavimas nenaudojamas kaip bendros paskirties rūšiavimo algoritmas.
Skaičiavimo rūšiavimas yra veiksmingas, kai diapazonas yra ne didesnis nei rūšiuojamų objektų skaičius. Jis gali būti naudojamas neigiamoms įvesties reikšmėms rūšiuoti.
Dabar pažiūrėkime skaičiavimo rūšiavimo algoritmą.
Algoritmas
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
Skaičiavimo rūšiavimo algoritmo darbas
Dabar pažiūrėkime, kaip veikia skaičiavimo rūšiavimo algoritmas.
Norėdami suprasti skaičiavimo rūšiavimo algoritmo veikimą, paimkime nerūšiuotą masyvą. Per pavyzdį bus lengviau suprasti skaičiavimo rūšiavimą.
Tegul masyvo elementai yra -
1. Raskite maksimalų elementą iš pateikto masyvo. Leisti maks būti didžiausias elementas.
2. Dabar inicijuokite ilgio masyvą max + 1 turintis visus 0 elementų. Šis masyvas bus naudojamas elementų skaičiui išsaugoti duotame masyve.
3. Dabar turime saugoti kiekvieno masyvo elemento skaičių atitinkamame indekse skaičiavimo masyve.
Elemento skaičius bus saugomas kaip - Tarkime, kad masyvo elementas „4“ pasirodo du kartus, taigi 4 elemento skaičius yra 2. Taigi 2 yra saugomas 4thskaičiavimo masyvo padėtis. Jei kurio nors elemento masyve nėra, padėkite 0, t. y. tarkime, kad elemento „3“ masyve nėra, todėl 0 bus saugomas 3rdpadėtis.
Dabar išsaugokite kaupiamąją sumą skaičiuoti masyvo elementai. Tai padės sudėti elementus į tinkamą rūšiuoto masyvo indeksą.
Panašiai, kaupiamasis skaičiavimo masyvo skaičius yra -
4. Dabar suraskite kiekvieno pradinio masyvo elemento indeksą
Įdėję elementą į vietą, sumažinkite jo skaičių vienu. Prieš dedant 2 elementą, jo skaičius buvo 2, tačiau pastačius jį į teisingą vietą, naujas 2 elemento skaičius yra 1.
Panašiai po rūšiavimo masyvo elementai yra -
Linux gamintojas
Dabar masyvas yra visiškai surūšiuotas.
Skaičiavimo rūšiavimo sudėtingumas
Dabar pažiūrėkime, koks sudėtingas skaičiavimo rūšiavimas geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime skaičiavimo rūšiavimo erdvės sudėtingumą.
1. Laiko sudėtingumas
| Byla | Laikas | Sudėtingumas |
|---|---|---|
| Geriausias atvejis | O(n + k) | |
| Vidutinis atvejis | O(n + k) | |
| Blogiausiu atveju | O(n + k) |
Visais aukščiau nurodytais atvejais skaičiavimo rūšiavimo sudėtingumas yra toks pat. Taip yra todėl, kad algoritmas praeina n+k kartų, neatsižvelgiant į tai, kaip elementai yra išdėstyti masyve.
Skaičiavimo rūšiavimas yra geresnis nei palyginimu pagrįsta rūšiavimo technika, nes skaičiavimo rūšiavimo elementai nėra lyginami. Tačiau kai sveikieji skaičiai yra labai dideli, skaičiavimo rūšiavimas yra blogas, nes reikia sukurti tokio dydžio masyvus.
2. Erdvės sudėtingumas
| Erdvės sudėtingumas | O (maks.) |
| Stabilus | TAIP |
- Skaičiavimo rūšiavimo erdvės sudėtingumas yra O(max). Kuo didesnis elementų asortimentas, tuo sudėtingesnė erdvė.
Skaičiavimo rūšiavimo įgyvendinimas
Dabar pažiūrėkime, kaip skaičiavimo programos rūšiuojamos skirtingomis programavimo kalbomis.
Programa: Parašykite programą, skirtą skaičiavimo rūšiavimui įgyvendinti C kalba.
#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;></=> Išvestis
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.
Šis straipsnis neapsiribojo tik algoritmu. Taip pat aptarėme rūšiavimo sudėtingumo skaičiavimą, veikimą ir įgyvendinimą skirtingomis programavimo kalbomis.