In questo articolo discuteremo dell'algoritmo di ordinamento del conteggio. L'ordinamento conteggio è una tecnica di ordinamento basata sulle chiavi tra intervalli specifici. Nelle interviste di codifica o tecniche per ingegneri del software, gli algoritmi di ordinamento sono ampiamente richiesti. Quindi è importante discutere l’argomento.
Questa tecnica di ordinamento non esegue l'ordinamento confrontando gli elementi. Esegue l'ordinamento contando oggetti con valori chiave distinti come l'hashing. Successivamente, esegue alcune operazioni aritmetiche per calcolare la posizione dell'indice di ciascun oggetto nella sequenza di output. L'ordinamento di conteggio non viene utilizzato come algoritmo di ordinamento generico.
L'ordinamento con conteggio è efficace quando l'intervallo non è maggiore del numero di oggetti da ordinare. Può essere utilizzato per ordinare i valori di input negativi.
Ora vediamo l'algoritmo di counting sort.
matematica discreta con negazione
Algoritmo
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
Funzionamento dell'algoritmo di ordinamento dei conteggi
Ora vediamo il funzionamento dell'algoritmo di ordinamento del conteggio.
Per comprendere il funzionamento dell'algoritmo di ordinamento del conteggio, prendiamo un array non ordinato. Sarà più semplice comprendere l'ordinamento del conteggio tramite un esempio.
Lascia che gli elementi dell'array siano -
1. Trova l'elemento massimo dall'array dato. Permettere massimo essere l'elemento massimo.
2. Ora inizializza l'array di lunghezza massimo + 1 avendo tutti 0 elementi. Questo array verrà utilizzato per memorizzare il conteggio degli elementi nell'array specificato.
3. Ora dobbiamo memorizzare il conteggio di ciascun elemento dell'array nel relativo indice corrispondente nell'array count.
Il conteggio di un elemento verrà memorizzato come - Supponiamo che l'elemento dell'array '4' sia apparso due volte, quindi il conteggio dell'elemento 4 è 2. Quindi, 2 è memorizzato in 4thposizione dell'array di conteggio. Se qualche elemento non è presente nell'array, inserisci 0, ovvero supponiamo che l'elemento '3' non sia presente nell'array, quindi 0 verrà memorizzato in 3rdposizione.
git checkout
Ora, memorizza la somma cumulativa di contare elementi dell'array. Aiuterà a posizionare gli elementi nell'indice corretto dell'array ordinato.
Allo stesso modo, il conteggio cumulativo dell'array count è -
quanti tasti hanno le tastiere?
4. Ora trova l'indice di ciascun elemento dell'array originale
Dopo aver posizionato l'elemento al suo posto, diminuisci il suo conteggio di uno. Prima di posizionare l'elemento 2, il suo conteggio era 2, ma dopo averlo posizionato nella posizione corretta, il nuovo conteggio per l'elemento 2 è 1.
Allo stesso modo, dopo l'ordinamento, gli elementi dell'array sono:
Ora l'array è completamente ordinato.
Conteggio della complessità dell'ordinamento
Ora, vediamo la complessità temporale dell'ordinamento del conteggio nel caso migliore, nel caso medio e nel caso peggiore. Vedremo anche la complessità spaziale dell'ordinamento di conteggio.
1. Complessità temporale
| Caso | Tempo | Complessità |
|---|---|---|
| Caso migliore | O(n+k) | |
| Caso medio | O(n+k) | |
| Caso peggiore | O(n+k) |
In tutti i casi sopra indicati, la complessità temporale dell'ordinamento del conteggio è la stessa. Questo perché l'algoritmo va a buon fine n+k volte, indipendentemente da come gli elementi sono posizionati nell'array.
L'ordinamento di conteggio è migliore delle tecniche di ordinamento basate sul confronto perché non esiste alcun confronto tra gli elementi nell'ordinamento di conteggio. Ma quando i numeri interi sono molto grandi, l'ordinamento del conteggio non è corretto perché è necessario creare array di quella dimensione.
2. Complessità spaziale
| Complessità spaziale | O(massimo) |
| Stabile | SÌ |
- La complessità spaziale dell'ordinamento di conteggio è O(max). Maggiore è la gamma di elementi, maggiore è la complessità dello spazio.
Implementazione del counting sort
Vediamo ora i programmi di ordinamento dei conteggi nei diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'ordinamento per conteggio in linguaggio 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;></=> Produzione
stringa java
Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo.
Questo articolo non si limitava solo all'algoritmo. Abbiamo anche discusso la complessità, il funzionamento e l'implementazione del conteggio dell'ordinamento in diversi linguaggi di programmazione.