Trier une liste chainée ?

Signaler
Messages postés
122
Date d'inscription
mercredi 16 avril 2003
Statut
Membre
Dernière intervention
22 juillet 2006
-
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
-
Bonjour,

Je voudrais connaitre le principe du trie dans une liste chainée.
Je voudrais par ex trier une liste chainée qui existe déjà et qui contient des infos en vrac. Comment faire ?
est ce que qq'un connaitrait un bon tuto là dessus ?

Merci

Tintin 72

4 réponses

Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
Tu as la méthode sort défini pour la classe list, il suffit que la
classe que tu utilises dans la liste dispose d'un opérateur de
comparaison (operator<). Si tu veux connaitre l'algorithme lui même,
tu peux chercher sur ce site: tri rapide, fusion, pas tas... Sachant
que certains conviennent mieux au liste chainées, et d'autres au
tableaux. Si tu utilise list::sort, tu es à peu près sur d'obtenir le
meilleur résultat possible
Messages postés
63
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
25 juillet 2005

dans une liste chainée, c pas très commode

Le mieux est d'utiliser la fonction sort de la stl, elle est en O(n log n)
Messages postés
122
Date d'inscription
mercredi 16 avril 2003
Statut
Membre
Dernière intervention
22 juillet 2006

Merci pour vos réponses, mais je n'arrive pas à trouver un tuto ou un exemple qui réponde clairement à ma question.
Par ex pour trier une liste chainée existante.
Est ce que le trie et la mise en ordre s'effectue dans la liste chainée ou est ce qu'il faut créer une autre liste pour y recopier les données dans l'ordre, (un peu à la manière des ajouts suppressions dans un tableau) ?

Tintin 72
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
exemple:

list l;

l.push_back(0);

...

l.sort();



Le tri se fait directement sur la liste existante