Counting Sort
Les algorithmes de tri tels que
Merge Sort effectuent un nombre d’opérations de l’ordre de pour trier une séquence donnée d’éléments. La plupart des fonctions sort() intégrées dans différents langages de programmation utilisent également un temps de l’ordre de . On peut alors se demander s’il existe un moyen de trier encore plus rapidement.Un algorithme de base qui permet de trier une séquence d’éléments en temps linéaire, c’est-à-dire avec un nombre d’opérations de l’ordre de , est l’algorithme Counting Sort. Il s’agit d’un algorithme de tri très performant, fonctionnant en temps linéaire et particulièrement adapté lorsque les éléments à trier sont des valeurs entières de petite taille.
Le principe fondamental du Counting Sort est d’utiliser une structure sous forme d’histogramme pour compter le nombre d’occurrences de chaque valeur dans la collection initiale, puis d’utiliser ces informations pour réordonner les éléments dans l’ordre souhaité.
Ainsi, pour trier un tableau comportant les valeurs
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], on construit un histogramme qui indique, par exemple, qu’il y a 6 occurrences de 1, 2 occurrences de 2, 5 occurrences de 3, etc. : [6, 2, 5, 4, 5, 1, 6, 1] (comme illustré sur l’image).
a = ...
bottom, top = min(a), max(a) + 1 # Déterminer la plage
hist = [0] * (top - bottom) # Remplir la plage avec des zéros => aucune occurrence
for num in a: # Parcourir le tableau
hist[num - bottom] += 1 # Incrémenter la valeur de l'histogramme
res = [] # Initialiser le tableau de résultats
for num in range(bottom, top): # Parcourir la plage
res += [num] * hist[num - bottom] # Ajouter autant de num au résultat que la valeur de l'histogrammeÀ la fin, le résultat contiendra
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].Notez que cette méthode fonctionne uniquement sur des nombres, en particulier des nombres de petite taille, alors que d’autres algorithmes comme
Bubble sort ou Merge sort peuvent s’appliquer à tout type d’éléments pourvu qu’on puisse les comparer.En pratique, l’algorithme réalise un total d’opérations de l’ordre de , où
n est le nombre d’éléments dans le tableau initial et r représente l’étendue des valeurs présentes. Cette approche peut être particulièrement rapide comparée à d’autres algorithmes comme Merge sort lorsque le jeu de données comporte des nombres dans une plage de valeurs relativement petite.🤔
Existe-t-il d’autres algorithmes de tri en temps linéaire?
Oui, par exemple le Radix-sort. Néanmoins, ces derniers ne fonctionnent que sur des nombres.
Si l’on se limite aux algorithmes de tri basés sur la comparaison, qui peuvent fonctionner sur tout type de séquence pourvu que l’on puisse comparer les éléments, alors le meilleur temps de tri possible reste de l’ordre de , et pas moins.
Entrée
La première ligne d’entrée contient un entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces, notés (-100 ≤ ≤ 100).Sortie
Le programme doit afficher les
n entiers, séparés par un espace, dans l’ordre croissant.Exemples
Input | Output |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB