Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
1668 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  tri pigeonnier

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

tri pigeonnier

n°537840
os2
Posté le 13-10-2003 à 05:50:27  profilanswer
 

j'ai entendu parlé du tri pigeonnier mais pas vu grand chose sur le web...
 
je cherche une adresse...


---------------
Borland rulez: http://pages.infinit.net/borland
mood
Publicité
Posté le 13-10-2003 à 05:50:27  profilanswer
 

n°537847
Taz
bisounours-codeur
Posté le 13-10-2003 à 07:27:23  profilanswer
 

c'est pas la même chose que la trieuse ? tu as N éléments indexables   contenu dans un tableau de >=N emplacements -> tu mets chaque élément à sa place ?
 
http://www.nist.gov/dads/HTML/bucketsort.html


Message édité par Taz le 13-10-2003 à 07:30:48
n°538445
os2
Posté le 13-10-2003 à 16:58:37  profilanswer
 

Taz a écrit :

c'est pas la même chose que la trieuse ? tu as N éléments indexables   contenu dans un tableau de >=N emplacements -> tu mets chaque élément à sa place ?
 
http://www.nist.gov/dads/HTML/bucketsort.html


 
très possible


---------------
Borland rulez: http://pages.infinit.net/borland
n°538481
MagicBuzz
Posté le 13-10-2003 à 17:20:51  profilanswer
 

C'est pas très performant ce style de tri... Rapide, mais carrément gourmand en ressources...
 
En fait, ce tri n'est intéressant que si n < N (avec n = borne maximale et N nombre d'éléments)
 
A ce moment, en plus de trier, cet algo permet de "compresser" les données, puisque tu supprimes les doublons sans perdre l'information.
 
Enfin... C'est bien ce que je pense hein ?
 
Mettons le tableau :
 
a[0] = 5;
a[1] = 4;
a[2] = 1;
a[3] = 4;
a[4] = 2;
a[5] = 0;
a[6] = 3;
a[7] = 2;
a[8] = 5;
a[9] = 4;
a[10] = 0;
a[11] = 1;
a[12] = 2;
a[13] = 1;
a[14] = 4;
 
Ca donne :
 
b[0] = 2;
b[1] = 3;
b[2] = 3;
b[3] = 1;
b[4] = 4;
b[5] = 2;
 
=> On passe de 15 lignes à 6 lignes.
=> Les éléments sont ordonnés
 
Par contre, imaginons un tableau :
 
a[0] = 15;
a[1] = 0;
a[2] = 65465465465;
 
Et là on pleure :D

n°592121
Giz
Posté le 16-12-2003 à 20:21:53  profilanswer
 

Cela s'appelle plus précisément le tri par comptage (Counting sort en anglais)...c'est l'algorithme LE PLUS performant en terme d'utilisation CPU.
Cependant de GROS inconvénients :
 
1) Si l'écart entre la valeur min et la valeur max de ton tableau initial est énorme, ton tableau de distribution sera lui aussi enorme => complexité mémoire TROP importante.
 
2) Aucune comparaison n'est faite entre les valeurs => impossible de rendre ce tri GENERIQUE s'appliquant à tout type de données (par exemple trier un tableau de structure)car aucune fonction de comparaison n'est utilisée.
 
Ce type de tri est donc réservé que dans dans cas bien précis connue de l'utilisateur :
 
Par exemple en imagerie, trié un tableau contenant les differents niveau de gris d'une image : on sait dc que les valeurs seront comprises entre 0 et 255 => le tableau de distribution sera petit et triera très vite le tableau en un temps linéaire.

n°592336
LeGreg
Posté le 17-12-2003 à 10:17:48  profilanswer
 

Citation :

1) Si l'écart entre la valeur min et la valeur max de ton tableau initial est énorme, ton tableau de distribution sera lui aussi enorme => complexité mémoire TROP importante.


 
Rien ne t'empeche de faire plusieurs passes,
pour trier un entier ou un flottant stocké sur 32 bits
quatre passes de tri et une passe de comptage avec quatre tableaux de 256 compteurs suffisent.
 

Citation :

2) Aucune comparaison n'est faite entre les valeurs => impossible de rendre ce tri GENERIQUE s'appliquant à tout type de données (par exemple trier un tableau de structure)car aucune fonction de comparaison n'est utilisée.


 
Il ne s'agit pas d'un tri de comparaison, les données à déplacer sont dans un ordre déjà connu, contrairement à des données quelconque a qui on aurait adjoint une fonction de comparaison sous forme de boite noire. Puisque les données sont déjà triées on peut les déplacer directement là où elles doivent se trouver.
 
LeGreg

n°592346
LeGreg
Posté le 17-12-2003 à 10:25:03  profilanswer
 

giz a écrit :


2) Aucune comparaison n'est faite entre les valeurs => impossible de rendre ce tri GENERIQUE s'appliquant à tout type de données (par exemple trier un tableau de structure)car aucune fonction de comparaison n'est utilisée.


 
Si tu peux ramener ton tri de structure à un comptage  
alors ça ne fait aucune différence.
Exemple: placer des mots dans un dictionnaire,
tu commences par regarder leur premieres lettre et si c'est P tu les mets directement dans la case P.
 
Le fait qu'il y ait un comptage est la uniquement pour rendre compte du fait qu'on cherche à avoir la structure la plus compacte (vecteur), bien évidemment s'il s'agit de mettre des objets dans des cases à contenance infinie (listes chainées), pas vraiment besoin de comptage.
 
LeGreg

n°592409
Taz
bisounours-codeur
Posté le 17-12-2003 à 12:30:42  profilanswer
 

giz a écrit :

Cela s'appelle plus précisément le tri par comptage (Counting sort en anglais)

non, ça ce n'est pas le tri par comptage. le tri par comptage, c'est pour chaque élément, tu comptes à combien d'éléments il est inférieure, tu l'insères, et tu recommences.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  tri pigeonnier

 

Sujets relatifs
Plus de sujets relatifs à : tri pigeonnier


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR