În acest articol, vom discuta despre algoritmul de sortare de numărare. Sortarea prin numărare este o tehnică de sortare care se bazează pe cheile dintre intervale specifice. În interviurile de codificare sau tehnice pentru inginerii de software, algoritmii de sortare sunt solicitați pe scară largă. Deci, este important să discutăm subiectul.
Această tehnică de sortare nu realizează sortarea prin compararea elementelor. Efectuează sortarea prin numărarea obiectelor cu valori cheie distincte, cum ar fi hashing. După aceea, efectuează câteva operații aritmetice pentru a calcula poziția indexului fiecărui obiect în secvența de ieșire. Sortarea de numărare nu este folosită ca algoritm de sortare de uz general.
Sortarea contorării este eficientă atunci când intervalul nu este mai mare decât numărul de obiecte de sortat. Poate fi folosit pentru a sorta valorile negative de intrare.
Acum, să vedem algoritmul de sortare de numărare.
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
Algoritmul de sortare de numărare
Acum, să vedem funcționarea algoritmului de sortare de numărare.
bandă de bază vs bandă largă
Pentru a înțelege funcționarea algoritmului de sortare de numărare, să luăm o matrice nesortată. Va fi mai ușor de înțeles sortarea de numărare printr-un exemplu.
Fie elementele matricei sunt -
1. Găsiți elementul maxim din tabloul dat. Lăsa max fi elementul maxim.
2. Acum, inițializați matricea de lungime max + 1 având toate cele 0 elemente. Această matrice va fi folosită pentru a stoca numărul elementelor din matricea dată.
3. Acum, trebuie să stocăm numărul fiecărui element de matrice la indexul corespunzător din tabloul de numărare.
Numărul unui element va fi stocat ca - Să presupunem că elementul de matrice „4” apare de două ori, deci numărul elementului 4 este 2. Prin urmare, 2 este stocat la 4thpoziţia matricei de numărare. Dacă niciun element nu este prezent în matrice, plasați 0, adică să presupunem că elementul „3” nu este prezent în matrice, deci, 0 va fi stocat la 3rdpoziţie.
Acum, stocați suma cumulativă a numara elemente de matrice. Va ajuta să plasați elementele la indexul corect al matricei sortate.
În mod similar, numărul cumulativ al matricei de numărare este -
4. Acum, găsiți indexul fiecărui element din tabloul original
După ce ați plasat elementul la locul său, micșorați-i numărul cu una. Înainte de a plasa elementul 2, numărul său era 2, dar după ce l-a plasat în poziția corectă, noul număr pentru elementul 2 este 1.
algebră relațională în rdbms
În mod similar, după sortare, elementele matricei sunt -
Acum, matricea este complet sortată.
Numărarea complexității sortării
Acum, să vedem complexitatea de timp a sortării numărării în cel mai bun caz, în cazul mediu și în cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a tipului de numărare.
1. Complexitatea timpului
| Caz | Timp | Complexitate |
|---|---|---|
| Cel mai bun caz | O(n + k) | |
| Caz mediu | O(n + k) | |
| Cel mai rău caz | O(n + k) |
În toate cazurile de mai sus, complexitatea de timp a sortării numărării este aceeași. Acest lucru se datorează faptului că algoritmul trece n+k ori, indiferent de modul în care sunt plasate elementele în matrice.
Sortarea de numărare este mai bună decât tehnicile de sortare bazate pe comparație, deoarece nu există nicio comparație între elemente în sortarea de numărare. Dar, când numerele întregi sunt foarte mari, sortarea de numărare este proastă, deoarece trebuie create matrice de această dimensiune.
sql ordine aleatorie
2. Complexitatea spațială
| Complexitatea spațială | O(max) |
| Grajd | DA |
- Complexitatea spațială a sortării numărării este O(max). Cu cât este mai mare gama de elemente, cu atât este mai mare complexitatea spațiului.
Implementarea sortării de numărare
Acum, să vedem programele de sortare de numărare în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa sortarea de numărare în limbajul C.
#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;></=> Ieșire
Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ.
Acest articol nu sa limitat doar la algoritm. De asemenea, am discutat despre numărarea complexității sortării, funcționarea și implementarea în diferite limbaje de programare.