En aquest article, parlarem de l'algoritme d'ordenació de recompte. L'ordenació per recompte és una tècnica d'ordenació que es basa en les claus entre intervals específics. A les entrevistes de codificació o tècniques per a enginyers de programari, els algorismes d'ordenació es demanen àmpliament. Per tant, és important parlar del tema.
Aquesta tècnica d'ordenació no realitza l'ordenació mitjançant la comparació d'elements. Realitza l'ordenació comptant objectes que tenen valors clau diferents, com ara hashing. Després d'això, realitza algunes operacions aritmètiques per calcular la posició de l'índex de cada objecte a la seqüència de sortida. L'ordenació per recompte no s'utilitza com a algorisme d'ordenació de propòsit general.
com convertir de cadena a int
L'ordenació de recompte és efectiva quan l'interval no és superior al nombre d'objectes que s'han d'ordenar. Es pot utilitzar per ordenar els valors d'entrada negatius.
Ara, anem a veure l'algorisme d'ordenació de recompte.
Algorisme
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
Funcionament de l'algorisme d'ordenació de recompte
Ara, vegem el funcionament de l'algoritme d'ordenació de recompte.
Per entendre el funcionament de l'algorisme d'ordenació de recompte, prenem una matriu no ordenada. Serà més fàcil entendre l'ordenació de recompte mitjançant un exemple.
Siguin els elements de la matriu -
1. Trobeu l'element màxim de la matriu donada. Deixar màx ser l'element màxim.
2. Ara, inicialitzeu la matriu de longitud màxim + 1 amb els 0 elements. Aquesta matriu s'utilitzarà per emmagatzemar el recompte dels elements de la matriu donada.
3. Ara, hem d'emmagatzemar el recompte de cada element de la matriu al seu índex corresponent a la matriu de recompte.
El recompte d'un element s'emmagatzemarà com a - Suposem que l'element de matriu '4' apareix dues vegades, de manera que el recompte de l'element 4 és 2. Per tant, 2 s'emmagatzema al 4thposició de la matriu de recompte. Si no hi ha cap element a la matriu, col·loqueu 0, és a dir, suposem que l'element '3' no està present a la matriu, per tant, 0 s'emmagatzemarà a 3rdposició.
Ara, emmagatzema la suma acumulada de comptar elements de matriu. Ajudarà a col·locar els elements a l'índex correcte de la matriu ordenada.
De la mateixa manera, el recompte acumulat de la matriu de recompte és -
4. Ara, troba l'índex de cada element de la matriu original
Després de col·locar l'element al seu lloc, reduïu el seu recompte en un. Abans de col·locar l'element 2, el seu recompte era 2, però després de col·locar-lo a la seva posició correcta, el nou recompte de l'element 2 és 1.
De la mateixa manera, després d'ordenar, els elements de la matriu són -
Ara, la matriu està completament ordenada.
Comptant la complexitat de l'ordenació
Ara, vegem la complexitat temporal de l'ordenació del recompte en el millor dels casos, en el cas mitjà i en el pitjor dels casos. També veurem la complexitat espacial del tipus de recompte.
1. Complexitat temporal
| Caixa | Temps | Complexitat |
|---|---|---|
| Millor cas | O(n + k) | |
| Cas mitjà | O(n + k) | |
| Pitjor dels casos | O(n + k) |
En tots els casos anteriors, la complexitat temporal de l'ordenació del recompte és la mateixa. Això es deu al fet que l'algoritme passa n+k vegades, independentment de com es col·loquen els elements a la matriu.
L'ordenació per recompte és millor que les tècniques d'ordenació basades en comparacions perquè no hi ha cap comparació entre els elements en l'ordenació per recompte. Però, quan els nombres enters són molt grans, l'ordenació de recompte és dolenta perquè s'han de crear matrius d'aquesta mida.
2. Complexitat espacial
| Complexitat espacial | O (màx.) |
| Estable | SÍ |
- La complexitat espacial de l'ordenació de recompte és O(max). Com més gran sigui la gamma d'elements, més gran serà la complexitat de l'espai.
Implementació de l'ordenació de recompte
Ara, anem a veure els programes d'ordenació de recompte en diferents llenguatges de programació.
Programa: Escriu un programa per implementar l'ordenació de recompte en llenguatge 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;></=> Sortida
inttostr java
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.
Aquest article no es limitava només a l'algorisme. També hem parlat del recompte de la complexitat de l'ordenació, el funcionament i la implementació en diferents llenguatges de programació.