- En cours de comptage
- Déplacée à l'instant
- En place
Tri par comptage
Le tri par comptage fonctionne quand les valeurs sont des nombres entiers dans un petit intervalle. Il garde un compteur pour chaque valeur possible, compte combien de fois chacune apparaît et, grâce à ces comptes, sait exactement où va chaque valeur. Regardez les compteurs se remplir pendant la lecture de la liste, puis se vider à mesure que chaque valeur rejoint son bloc, un déplacement à la fois. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'un déplacement à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. La bande entre la liste et la rangée tampon contient un compteur par valeur. Les tuiles indiquent les valeurs comptées, les déplacements et les compteurs. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez le nombre de barres et leur ordre de départ, ou saisissez vos propres nombres entiers. Essayez une liste avec peu de valeurs distinctes.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une valeur à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
- Suivez les compteurs : ils se remplissent pendant la lecture de la liste, puis redescendent à mesure que chaque valeur est placée.
Comment fonctionne le tri par comptage
Créez un compteur pour chaque valeur, de la plus petite à la plus grande. Lisez la liste une fois et ajoutez un au compteur de chaque valeur rencontrée. Additionnez ensuite les comptes à partir de la plus petite valeur : le bloc d'une valeur commence juste après toutes les valeurs plus petites. Enfin, parcourez de nouveau la liste, placez chaque valeur à la prochaine place libre de son bloc et recopiez le résultat.
Rapide sur un petit intervalle
Le tri par comptage lit la liste deux fois et parcourt les compteurs une fois : son travail croît donc avec n + k, le nombre de valeurs plus le nombre de compteurs. Pour beaucoup de valeurs dans un petit intervalle, comme des notes d'examen de 0 à 100 ou des âges, il bat tout tri par comparaison. Sur un intervalle large, il gaspille du temps et de la mémoire en compteurs inutiles : trois valeurs réparties de 1 à 1 000 000 demanderaient un million de compteurs. C'est aussi l'étape que le tri par base répète pour chaque chiffre.
Questions fréquemment posées
Comment fonctionne le tri par comptage ?
Il compte combien de fois chaque valeur apparaît, additionne les comptes pour savoir où commence le bloc de chaque valeur, puis place chaque valeur directement à la prochaine place libre de son bloc. Il ne compare jamais deux valeurs.
Quand utiliser le tri par comptage ?
Quand les valeurs sont des nombres entiers, ou peuvent le devenir, et que l'intervalle de la plus petite à la plus grande n'est pas beaucoup plus grand que le nombre de valeurs : notes, âges, petits codes. Il prend alors un temps proportionnel à n + k.
Le tri par comptage est-il stable ?
Oui, quand les valeurs sont déplacées dans l'ordre de la liste vers la prochaine place libre de leur bloc, comme ici. C'est ce qui permet au tri par base de l'utiliser pour chaque chiffre.
Pourquoi ne pas simplement écrire chaque valeur autant de fois qu'elle a été comptée ?
Pour de simples nombres, cela marche, et c'est même plus simple. Mais les données réelles contiennent souvent plus que la clé, comme un nom avec chaque note, et écrire les clés comptées le ferait perdre. Déplacer les éléments eux-mêmes garde tout ensemble.
Mes nombres sont-ils envoyés quelque part ?
Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur