Discussion :

[Margatthieu]

Bonjour,

Je débute en algo, et je cherche un moyen de trier une liste accessible par pointeurs.

Je commence par comparer la tete de la liste au suivant.
Si superieur, je passe au pointeur suivant, sinon j'insere, et ansi de suite jusqu'a la queue de la liste.

Mais comment savoir combien de "tours" je dois faire ?

Pour un tableau classique, il suffit de faire la même iteration avec la 2eme case et ansi de suite.
Mais avec des pointeurs, je vois pas ...

Merci pour vos conseils
Matthieu

[Zavonen]

Appelons ta liste L1
A mon avis, le meilleur moyen est de créer une nouvelle liste vide au départ, L2
Tu mets en tête de L2 la tête de L1
puis tu prends le second terme de L1, s'il est inférieur au premier terme de L2 tu le mets en tête, sinon en queue.
Et ainsi de suite tu parcoures L1 et tu places chaque nouvel élément à sa place dans L2 qui est, elle, toujours triée. (C'est un tri par insertion)
A la fin ton résultat est dans L2
Autre possibilité: si tu dois trier 'en place' (recopie interdite), alors là, le mieux est d'implémenter le tri 'à bulles', (il te suffit de savoir inverser deux éléments consécutifs-mais attention au cas particuliers des deux extrêmes) car avec des listes chainées, les algos plus élaborés risquent d'être difficiles à implémenter, spécialement si tu ne disposes pas d'indices pour les repérer, s'il y a des doublons etc, c'est plein de peaux de banane).
Est-ce assez clair ?

Mais comment savoir combien de "tours" je dois faire ?

Disons n-1 tours où n est le nombre d'éléments de la liste (comme pour un tableau)

[Jedai]

Autre possibilité: si tu dois trier 'en place' (recopie interdite), alors là, le mieux est d'implémenter le tri 'à bulles', (il te suffit de savoir inverser deux éléments consécutifs-mais attention au cas particuliers des deux extrêmes) car avec des listes chainées, les algos plus élaborés risquent d'être difficiles à implémenter, spécialement si tu ne disposes pas d'indices pour les repérer, s'il y a des doublons etc, c'est plein de peaux de banane).
Est-ce assez clair ?

Le tri fusion est très simple à implémenter avec des listes chaînées.

--
Jedaï

[Margatthieu]

Merci pour vos conseils

Le tri par insertion me parait simple
Je vais également jeter un oeil sur le tri par fusion

Merci et a+
Matthieu