Algoritmo di ordinamento conteggio

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.