Discuter:Tri comptage

Un article de Wikipédia, l'encyclopédie libre.

	Tri comptage fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début	Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Faible	Cet article a été classé comme d'Importance faible selon le Tableau d'évaluation du projet. (Contester?)

j'aimerais avoir un exemple d'algorithme de Tri comptage

[modifier] Tri par comptage ?

Je crois que j'ai mal compris la définition du tri par comptage en suivant le début de l'article wikipedia déjà existant, et donc ce que j'ai écrit est faux. En tout cas, c'est différent de ce qui est expliqué ici : http://progfrance.tuxmania.org/index.php/Algorithme_:_Tri_par_comptage La définition, telle que je l'ai comprise est discutée ici : http://forum.hardware.fr/hardwarefr/Programmation/pigeonnier-sujet-42382-1.htm C'est surtout une question d'appellation, et je me renseigne pour être certain que l'article est correct. Scullder 13 juin 2006 à 20:32 (CEST)

Après vérification, ça me semble bon. Scullder 13 juin 2006 à 22:57 (CEST)

[modifier] Tri comptage et Tri par dénombrement

J'ai un doute concernant la différence entre le tri comptage, et le tri par dénombrement. Tout d'abord, est-ce deux tris différents ?

Secondo : Lors du tri par comptage, le tableau intermédiaire est-il censé contenir la fréquence de chaque valeurs ou plutôt le nombre de valeurs qui lui sont inférieures ?

J'ai modifié l'algorithme initialement présent, car il avait quelques soucis, et j'ai également fait l'algorithme qui suit la règle du tableau avec le nombre de valeurs inférieures (sûrement avec quelques erreurs à corriger).

Il faudrait également voir si il faut créer un article sur le Tri par dénombrement, ou inclure son nom dans l'article (le tri par dénombrement étant la traduction de Counting Sort dans la version française de Introduction à l'algorithmique de Cormen, Rivest et al.).

En espérant avoir des réponses.

fonction tri_par_comptage(tableau tab, entier borne_superieure)
 
   /* Initialisation des variables */
 
   tab_comptage[borne_superieure + 1]
   taille_tab ⇐ taille(tab)
 
   /* Initialisation du tableau de comptage à 0 */
 
   Pour i ⇐ 1 Jusqu'à borne_superieure
   Faire
      tab_comptage[ i ] ⇐ 0
   FinPour
 
   /* Création du tableau de comptage */
 
   Pour i ⇐ 1 Jusqu'à taille_tab
   Faire
      tab_comptage[ tab[ i ] ] ⇐ tab_comptage[ tab[ i ] ] + 1
   FinPour
 
   /* Somme le tableau de comptage afin d'avoir le nombre de valeurs inférieures*/
 
   tab_comptage[borne_superieure] ⇐ taille_tab - tab_comptage[borne_superieure] + 1
   Pour i ⇐ borne_superieure - 1 Jusqu'à 1
   Faire
      tab_comptage[ i ] ⇐ tab_comptage[ i + 1 ] - tab_comptage[ i ]
   FinPour
 
   /* Création du tableau trié */
 
   Pour i ⇐ 1 Jusqu'à taille_tab
   Faire
      R[ tab_comptage[ tab[i] ] ] ⇐ tab_comptage[ tab[i] ]
      tab_comptage[ tab[i] ] ⇐ tab_comptage[ tab[i] ] + 1
   FinPour
 
 Retourne R

--Gium 3 septembre 2006 à 22:51 (CEST)

[modifier] Tri par dénombrement = Tri casier ?

J'ai trouvé un rapport de thèse qui parle de ce type de tri présenté comme tri par comptage sur wikipedia. Cela confirme les dires de Scullder. [1] Par poof65 le 15 septembre 2006 à 05:10 (CEST)