Dans ce didacticiel, vous apprendrez comment fonctionne le tri par comptage. Vous trouverez également des exemples pratiques de tri de comptage en C, C ++, Java et Python.
Le tri par comptage est un algorithme de tri qui trie les éléments d'un tableau en comptant le nombre d'occurrences de chaque élément unique du tableau. Le décompte est stocké dans un tableau auxiliaire et le tri est effectué en mappant le décompte en tant qu'index du tableau auxiliaire.
Comment fonctionne le tri par comptage?
- Découvrez l'élément maximum (que ce soit
max) du tableau donné.
Tableau donné - Initialisez un tableau de longueur
max+1avec tous les éléments 0. Ce tableau est utilisé pour stocker le nombre d'éléments dans le tableau.
Tableau de comptage - Stocker le compte de chaque élément à leur index respectif dans le
counttableau
Par exemple: si le compte de l'élément 3 est 2 alors, 2 est stocké dans la 3ème position du tableau de comptage. Si l'élément "5" n'est pas présent dans le tableau, alors 0 est stocké en 5ème position.
Nombre de chaque élément stocké - Stockez la somme cumulée des éléments du tableau de comptage. Cela aide à placer les éléments dans l'index correct du tableau trié.
Comptage cumulé - Recherchez l'index de chaque élément du tableau d'origine dans le tableau count. Cela donne le décompte cumulatif. Placez l'élément à l'indice calculé comme indiqué dans la figure ci-dessous.
Tri de comptage - Après avoir placé chaque élément à sa position correcte, diminuez son nombre de un.
Algorithme de tri par comptage
countingSort (array, size) max <- trouver le plus grand élément du tableau initialiser le tableau de comptage avec tous les zéros pour j <- 0 à la taille trouver le nombre total de chaque élément unique et stocker le nombre au jème index dans le tableau de comptage pour i <- 1 pour max trouver la somme cumulée et la stocker dans le tableau de comptage lui-même pour j <- taille jusqu'à 1 restaurer les éléments dans le tableau diminuer le nombre de chaque élément restauré de 1
Exemples Python, Java et 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); )
Complexité
Complexités temporelles:
Il y a principalement quatre boucles principales. (La recherche de la plus grande valeur peut être effectuée en dehors de la fonction.)
| boucle for | temps de comptage |
|---|---|
| 1er | O (max) |
| 2e | O (taille) |
| 3e | O (max) |
| 4e | O (taille) |
Complexité globale = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Pire complexité des cas:
O(n+k) - Meilleure complexité de cas:
O(n+k) - Complexité moyenne des cas:
O(n+k)
Dans tous les cas ci-dessus, la complexité est la même car peu importe la façon dont les éléments sont placés dans le tableau, l'algorithme passe par les n+ktemps.
Il n'y a pas de comparaison entre les éléments, c'est donc mieux que les techniques de tri basées sur la comparaison. Mais, c'est mauvais si les entiers sont très grands car le tableau de cette taille doit être créé.
Complexité de l'espace:
La complexité spatiale de Counting Sort est O(max). Plus la gamme d'éléments est grande, plus la complexité de l'espace est grande.
Comptage des applications de tri
Le tri par comptage est utilisé lorsque:
- il existe des nombres entiers plus petits avec plusieurs comptes.
- la complexité linéaire est le besoin.
