Probleme de tri par insertion dans une liste chainée

Bonjour,

J'ai une liste chainée de :

[fixed]  pointeur_ligne_top = ^t_ligne_top;
  t_ligne_top=record
    page:string[100];
    compteur:integer;
    suivant:pointeur_ligne_top;
    precedent:pointeur_ligne_top;
  end;[/fixed]

J'essaye de faire un tri par insertion, tri decroissant par rapport au "compteur".

Ma demarche :

Donc, si le compteur de la valeur actuelle (tmp^.compteur) est superieur au compteur precedent (tmp^.precedent^.compteur)

Alors, il va faloir refaire les liens de l'enregistrement actuel (tmp) pour l'inserer au bon endroit.

Pour cela, j'appelle ma 2eme fonction qui detecte cette endroit (objet_top_min) dans la partie basse de la liste.... puis je refais les liens.

Si tmp^.compteur est superieur a tous les compteurs de la partie basse, alors, je l'insere au tout debut et je redefinie la tete de la liste (tete_top) sinon, je l'inserer entre 2 valeurs....

Au niveau du code, j'arrive à ca :

function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var
  tmp : pointeur_ligne_top;
begin
  tmp := tete_top;

while ((tmp^.compteur > val) and (tmp^.suivant<>nil)) do
  begin
    tmp := tmp^.suivant;
  end;

  result := tmp^.precedent;
end;

procedure top_tri_insertion(var tete_top:pointeur_ligne_top);
var
  tmp: pointeur_ligne_top;
  objet_top_min : pointeur_ligne_top;
begin

  tmp := tete_top^.suivant;

  while tmp <> nil do
    begin

      if tmp^.compteur > tmp^.precedent^.compteur then
        begin

          objet_top_min := top_min_insertion(tete_top,tmp^.compteur);

          tmp^.precedent^.suivant := tmp^.suivant;

          if ((tmp^.compteur > tete_top.compteur) or (objet_top_min = nil)) then
            begin
              tmp^.suivant := tete_top;
              tmp^.precedent := nil;
              tete_top^.precedent := tmp;
              tete_top := tmp;
            end
          else
            begin
              tmp^.suivant := objet_top_min^.suivant;
              tmp^.precedent := objet_top_min;

              objet_top_min^.suivant^.precedent := tmp;
              objet_top_min^.suivant := tmp;
            end;
        end;

      //Form1.Memo1.Lines.Add(tmp^.page);
      tmp := tmp^.suivant;

    end;
    ShowMessage('Fin du tri');
end;

Et voila le resultat d'un tri. En 1er, il y a la liste non triée puis à la suite, il y a la liste "triée" (tout en bas...), Vous verrez que ca a zappé les 3/4 des valeurs...

http://www.gregserveur.com/test/stats_1.html (218 Ko)

MERCI de votre aide, car la je desespère. J'y ai passé la nuit et je trouve toujours pas.

procedure tri_insertion(var p:pointeur_ligne_top);

var

  q,r,s:pointeur_ligne_top;

begin

  q:=p;

  while Assigned(q.suivant) do begin

    r:=q.suivant;

    s:=r;

    while Assigned(r.precedent) and (r.precedent.compteur>s.compteur) do

      r:=r.precedent;

    if r<>s then begin

      q.suivant:=s.suivant;

      if Assigned(s.suivant) then

        s.suivant.precedent:=q;

      if Assigned(r.precedent) then begin

        r.precedent.suivant:=s;

        s.precedent:=r.precedent;

      end else begin

        p:=s;

        s.precedent:=nil;

      end;

      r.precedent:=s;

      s.suivant:=r;

    end else

      q:=q.suivant;

  end;

end;

Ca devrait marcher. Le problème de ton code, c'est que tu avançais dans la liste même si le dernier élément dont tu t'es occupé (temp) avait été déplacé vers la tête. Or, si c'est le cas, tu ne dois pas avancer dans la liste car en ayant déplacé un élément vers la tête, ça t'a déjà fait avancer (je ne sais pas si c'est très clair)...
Dans ma fonction, c'est le test

if r<>s

qui s'occupe de vérifier si c'est le cas ou non.

[img]http://www.eleves.ens.fr/home/feuvrier/signature.jpg[/img]