Frage zum Sortieren einer verketteten Liste

[xineohp]

so, ich hab noch mal drüber nachgedacht und hoffe nun eine endgültige (und endlich auch richtige) Lösung präsentieren zu können:

Mein letzter Ansatz mit zwei Hilfsvariablen war in sofern falsch, da ich die Problematik der von einander abhänigen Referenzen (siehe Anhang) nicht in letzter Konsequenz beachtet hatte.

Man benötigt nun mehr vier Hilfsvariablen (Erläuterungen hierzu im Anhang):

Delphi-Quellcode:

helpA := nav;
helpB := nav^.next;
helpC := nav^.next^.next;

help  := helpA;
helpA := helpB;
helpB := helpC;
helpC := help;

Die von mytar vorgeschlagenen Änderungen ändern sind nicht zwingend notwendige Verbesserungen. Die erste (Assinged) sichert das ganze zusätzlich ab, sollte aber auch ohne funktionieren (wenn der Tauschvorgang nun endlich stimmt). Die zweite stellt eine kleine Optimierung dar (aber nur wenn sie richtig implementiert wird! das changed := false steht nämlich an falscher Stelle es muss wenn dann innerhalb der repeat-Schleife stehen! Insgesammt spärt die repeat- gegenüber der while-Schleife eine Überprüfung der Abbruchsbedingung -_-
Trotzdem würde ich die Veränderungen übernehmen

Das Endergebnis sollte also folgendermaßen aussehen:

Delphi-Quellcode:

var
  changed: boolean;
  nav, help, helpA, helpB, helpC: tListenElement;
begin

  repeat
    changed := False;    //<<<
    nav := root;
    while Assigned(nav) and Assigned(nav^.next) do 
    begin
      if nav^.name > nav^.next^.name then
      begin
        helpA := nav;
        helpB := nav^.next;
        helpC := nav^.next^.next;

        help  := helpA;
        helpA := helpB;
        helpB := helpC;
        helpC := help;
       
        changed := True;
        if help = root then
         root := nav;   
      end;
      nav := nav^.next;                 
    end;
  until not changed; 
end;

EDIT: Anhang vergessen ...