In questo tutorial imparerai come funziona il conteggio dell'ordinamento. Inoltre, troverai esempi funzionanti di conteggio dell'ordinamento in C, C ++, Java e Python.
Il conteggio dell'ordinamento è un algoritmo di ordinamento che ordina gli elementi di un array contando il numero di occorrenze di ogni elemento univoco dell'array. Il conteggio viene memorizzato in un array ausiliario e l'ordinamento viene eseguito mappando il conteggio come indice dell'array ausiliario.
Come funziona l'ordinamento conteggio?
- Trova l'elemento massimo (lascia che sia
max) dall'array dato.
Dato array - Inizializza un array di lunghezza
max+1con tutti gli elementi 0. Questo array viene utilizzato per memorizzare il conteggio degli elementi nell'array.
Count array - Memorizza il conteggio di ogni elemento nel rispettivo indice
countnell'array
Ad esempio: se il conteggio dell'elemento 3 è 2, 2 viene memorizzato nella terza posizione dell'array di conteggio. Se l'elemento "5" non è presente nell'array, lo 0 viene memorizzato in quinta posizione.
Conteggio di ogni elemento memorizzato - Memorizza la somma cumulativa degli elementi della matrice di conteggio. Aiuta a posizionare gli elementi nell'indice corretto dell'array ordinato.
Conteggio cumulativo - Trova l'indice di ogni elemento dell'array originale nell'array count. Questo dà il conteggio cumulativo. Posizionare l'elemento all'indice calcolato come mostrato nella figura sotto.
Ordinamento di conteggio - Dopo aver posizionato ogni elemento nella posizione corretta, diminuirne il conteggio di uno.
Algoritmo di ordinamento conteggio
countingSort (array, size) max <- trova l'elemento più grande in array inizializza count array con tutti zeri per j <- 0 to size trova il conteggio totale di ogni elemento univoco e memorizza il conteggio in jth index in count array per i <- 1 per trovare al massimo la somma cumulativa e memorizzarla nell'array count stesso per j <- dimensione fino a 1 ripristinare gli elementi nell'array diminuire il conteggio di ogni elemento ripristinato di 1
Esempi di Python, Java e C / C ++
Python Java C C ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
Complessità
Complessità temporali:
Ci sono principalmente quattro cicli principali. (Trovare il valore massimo può essere fatto al di fuori della funzione.)
| for-loop | tempo di conteggio |
|---|---|
| 1 ° | O (massimo) |
| 2 ° | O (taglia) |
| 3 ° | O (massimo) |
| 4 ° | O (taglia) |
Complessità complessiva = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Peggiore complessità del caso:
O(n+k) - Migliore complessità del caso:
O(n+k) - Complessità media del case:
O(n+k)
In tutti i casi precedenti, la complessità è la stessa perché indipendentemente da come gli elementi siano inseriti nell'array, l'algoritmo passa attraverso i n+ktempi.
Non c'è confronto tra alcun elemento, quindi è meglio delle tecniche di ordinamento basate sul confronto. Ma è un male se gli interi sono molto grandi perché dovrebbe essere creato l'array di quella dimensione.
Complessità spaziale:
La complessità spaziale di Counting Sort è O(max). Maggiore è la gamma di elementi, maggiore è la complessità dello spazio.
Conteggio delle applicazioni di ordinamento
L'ordinamento conteggio viene utilizzato quando:
- ci sono numeri interi più piccoli con più conteggi.
- la complessità lineare è la necessità.
