INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q053 — Pourquoi counting sort n’est-il pas un tri par comparaison ? Donner sa complexité en fonction de n et de l’étendue k.
Je vous remercie pour cette question, que je vais traiter avec la rigueur qu'elle mérite. Pourquoi counting sort n'est pas un tri par comparaison Un tri par comparaison est un algorithme dont le comportement repose exclusivement sur des opérations de comparaison entre éléments, du type « a est-il inférieur à b ? ». La borne inférieure classique de Ω(n log n) pour ces tris découle précisément de cette restriction : avec n éléments, il existe n! permutations possibles, et chaque comparaison binaire ne peut au mieux éliminer que la moitié des cas restants, d'où un nombre minimal de comparaisons de l'ordre de log₂(n!). Counting sort, lui, n'effectue aucune comparaison entre les éléments à trier. Il exploite directement la valeur numérique des clés pour les compter et les placer. Son fonctionnement se décompose en trois phases : il compte d'abord le nombre d'occurrences de chaque valeur possible dans l'intervalle [0, k−1], puis il transforme ces comptages en positions cumulées, enfin il reconstruit le tableau trié en plaçant chaque élément à sa position définitive. Aucune de ces étapes ne compare deux éléments entre eux ; on compare seulement les clés à des bornes d'index, ce qui n'est pas une comparaison entre éléments. C'est pourquoi la borne Ω(n log n) ne s'applique pas à lui. Complexité en fonction de n et de k Soit n le nombre d'éléments et k l'étendue des valeurs possibles, c'est-à-dire le nombre de valeurs distinctes que peuvent prendre les clés. La phase de comptage parcourt le tableau de taille n, la phase de cumul parcourt l'intervalle de taille k, et la phase de reconstruction parcourt de nouveau n éléments. La complexité temporelle est donc : T(n, k) = O(n + k) La complexité spatiale, pour les tableaux auxiliaires de comptage et de sortie, est également O(n + k). Remarques importantes Ce tri est stable, ce qui le rend utile comme sous-programme du tri par base, ou radix sort. Il n'est avantageux que lorsque k est raisonnablement petit devant n ou comparable à n ; si k devient très grand, par exemple de l'ordre de 2³² pour des entiers 32 bits, la mémoire requise devient prohibitive et l'algorithme perd son intérêt. Il ne s'applique par ailleurs qu'à des clés entières ou discrètes, et non à des données quelconques comparables. Confiance : 96 %. Cette confiance reflète que la définition de la borne inférieure des tris par comparaison et la complexité O(n + k) de counting sort sont des résultats standard et solidement établis, que j'ai vérifiés par le raisonnement ; je laisse une petite marge car toute affirmation technique récitée de mémoire comporte une infime part d'incertitude, sans qu'aucun point de cette réponse ne me paraisse contestable.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.