Tri par insertion sur listes simplement chainées

Signaler
Messages postés
55
Date d'inscription
mardi 16 octobre 2007
Statut
Membre
Dernière intervention
15 novembre 2011
-
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
-
Bonjour,

voilà, je vous explique rapidement mon problème, je dois élaborer
une procédure de tri par insertion sur une liste qui vient en paramètre
de ma procédure.

Le seul petit problème c'est que ma liste est simplement chainée
donc je ne peux pas faire des précédent lors du parcours de ma liste.

J'aimerais savoir si vous avez une idée du codage à faire pour
faire ça. Je dois élaborer cette procédure en C/C++ (c'est à la fac il
l'appelle comme ça, il font un mélange des deux langages, moi-même je
n'ai pas compris pourquoi ^^).

Le prototype que je lui ai mis est le suivant :

-
Void Tri_Insertion_Liste(Liste &l, int Taille);


Merci de m'aider car je ne sais pas trop comment faire là-dessus.

Cordialement, Shinohinata

3 réponses

Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
salut

dans une liste chainee, la taille est sans importance.

le tri par insertion se fait comme ca :

Liste * inser_sort(Liste *l){
  Liste *li = NULL;
  while (l != NULL){
     li = inserrer(l->item, li);
     l = l->next;
  }
  return li;
}

il reste a coder la fonction d'insertion.
Messages postés
55
Date d'inscription
mardi 16 octobre 2007
Statut
Membre
Dernière intervention
15 novembre 2011

la fonction d'insertion ne sera pas à coder à part dans mon cas c'est un des impératifs. Tout doit se résumer en une seule procédure. Donc il faudra que je puisse remplacer le :
li  = insérer(li->item, li); par autre chose enfin par le code de cette fonction.

Si je suppose bien il ne doit pas être bien long.
La fonction insérer doit juste insérer si je ne m'abuse pour ce qui est du tri c'est la présente boucle qui s'en occupe.
Si ce n'est pas le cas je vais devoir prendre l'élément courant de la liste l puis le comparer à tout les éléments de cette même liste pour voir si il y en a un plus petit et si c'est le cas les 2 éléments s'inverse et ce pour chaque élément de la liste jusqu'à avoir tout parcouru ?

J'aime pas ce tri par insertion il m'embrouille -_-
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
l'insertion c'est une simple boucle...