Frage zum Sortieren einer verketteten Liste

[Chris P]

HI Leute,

was ist sinnvoller beim Sortieren einer einfach verketteten Liste:

Wenn man die Inhalte der Elemente sortiert oder die Zeiger ansich.

Ich benutze den Bubblesort.


Was würdet ihr emfehlen?

[neolithos]

Immer den Zeiger an sich.

Du wirst aber wahrscheinlich 3 Zeiger füren müssen.

Code:

Prev
Current <- Die beiden werden 
Next    <- verglichen

[Chris P]

Hier meine Prozedur:

Delphi-Quellcode:

procedure TForm1.SortList();
var
   Loop1, Loop2: Integer;
   Nav : PZeiger;
   Help: PZeiger;
begin

   Nav := Root;

   for Loop1 := 1 to 4 do
   begin
      for Loop2 := Loop1 to 4 do
      begin
         if Nav^.Name > Nav^.Next^.Name then
         begin
            Help := Nav;
            Nav := Nav^.Next;
            Nav^.Next := Help;
         end;
      Nav := Nav^.Next;
      end;
   Nav := Root;
   end;
   
end;

Aber es funktioniert nicht.
Die Zahl 4 in der FOR-Schleife ist die Anzahl der Elemente
Wo liegt der Fehler?
Bräuchte man noch einen 2. Hilfszeiger?

[xineohp]

moin,

kann sein, dass ich das jetzt irgendwie falsch interpretiere, aber willstu die Liste nicht nach dem Inhalt sortieren? Sonst sortierst du doch lediglich eine Liste mit Speicheradressen?! :gruebel:
EDIT: hab übersehen, das du das schon tust, sorry. :oops:

[Chris P]

Die Inhalte der Elemente werden nur miteinander verglichen und dann die entsprechenden
Adressen vertauscht. Dadurch sollte die Liste eigentlich sortiert sein!

Geht aber leider nicht...

[xineohp]

kann es sein, dass du den Tauschvorgang jedesmal wieder rückgängig machst? Ich glaube, die zwei auskommentierten Zeilen sind falsch/überflüssig.

Zitat:

Zitat von Chris P

Delphi-Quellcode:

procedure TForm1.SortList();
var
   Loop1, Loop2: Integer;
   Nav : PZeiger;
   Help: PZeiger;
begin

   Nav := Root;

   for Loop1 := 1 to 4 do
   begin
      for Loop2 := Loop1 to 4 do
      begin
         if Nav^.Name > Nav^.Next^.Name then
         begin
            Help := Nav;
            Nav := Nav^.Next;
            Nav^.Next := Help;
         end;
      // Nav := Nav^.Next;
      end;
   // Nav := Root;
   end;
   
end;

EDIT: ich befürcht ich hab schon wieder Quark geschrieben :oops:
EDIT2: ich glaub ich muss mal ein paar Minuten nachdenken.

[atreju2oo0]

Der Quelltext müsste eigentlich stimmen nur ein Fehler ist drin.
Bei Bubblesort muss man den Algo sooft anwenden bis keine Verschiebung mehr
vorkommt. Deshalb ist er ja auch relativ langsam. Besser wäre IMO Quicksort zu benutzen,
da sich das mit Zeigern eh sehr schön lösen lässt.

[Chris P]

Das 1. auskommentierte setzt doch den Laufzeiger auf das nächste Element.
Denn dann wird doch das nächste Element verglichen.

Das 2. muss auch sein denn die Liste muss wieder von Anfang durchlaufen werden.

Bsp: Wenn das Element mit dem größten Inhalt ganz nach rechts geschoben wird, muss man wieder von vorne anfangen und das zweit größte Element nach rechts schieben.

Das ist der normale Bubblesort

[neolithos]

Nicht getestet:

So sieht Bubblesort aus!!!

Delphi-Quellcode:

var pPrevPrev,
    pPrev,
    pNext : PList;

begin
  // nur anwenden wenn mindestens ein Element enthalten
  pPrevPrev := nil;
  pPrev := pFirst;
  pCur := pFirst^.pNext;
  repeat
    lSwap := false;
    
    while pCur <> nil do
      begin
        if nicht richtige reihenfolge zwischen pPrev und pCur then
           begin
             pPrevPrev^.pNext := pCur;
             pCur^.pNext := pPrev;
             pPrev^.pNext := pCur^.pNext;
             lSwap := true;
           end;
        // Nächster
        pPrevPrev := pPrev;
        pPrev := pCur;
        pCur := pCur^.pNext;
      end;

  until lSwap;
end;

[Chris P]

Zitat:

if nicht richtige reihenfolge zwischen pPrev und pCur then

Was bedeutet das?

[Chris P]

Kann mir bitte jemand helfen

[xineohp]

so,

jetzt hab ich 's:

Bei einer einfach verküpften Liste müssen 3! Zeiger verändert werden, du brauchst also zwei Hilfsvariablen.

Delphi-Quellcode:

var
  changed: boolean;
  nav, help1, help2: tListenElement;
begin

  changed := true;
  while changed do   // deine Version mit der zweiten Schleife sollte auch funktionieren, 
  begin              // aber so muss du die Anzahl der Elemente der Liste nicht kennen.
    changed := false;
    nav := root;                            // Zeiger auf den Anfang setzen
    while not (nav^.next = nil) do          // solange wir nicht am Ende sind weiter machen
    begin
      If nav^.name > nav^.next^.name then   // vergleichen 
      begin
        help1 := nav;                       // die zwei Elemente vertauschen. 
        nav := nav^.next;                   // man beachte, dass hierzu drei Zeiger geändert werden müssen!
        help2 := nav^.next;
        nav^.next := ´nav^.next^.next;
        help2^.next := help1;
        changed := true;
        If help1=root then root := nav;     // falls wir gerade das root-Element geändert haben, root neu setzen  
      end;
      nav := nav^.next;                     // auf zum nächsten Element :) 
    end;
  end;

end;

[Chris P]

Funktioniert aber nicht ganz.

Was macht eigentlich der 2. Hilfszeiger.
Ich habe in meiner Liste 5 Elemente.
Die 2. WHILE - Schleife läuft nur 4 mal durch und dann kommt eine Zugriffsverletzung.

Wo liegt der Fehler???

Hast du es schon getestet?

[mytar]

Ersetze die 2. While-Anweisung mit:

Delphi-Quellcode:

while Assigned(nav) and Assigned(nav^.next) do

greetz
mytar :-D

[mytar]

Noch eine Änderung:

Delphi-Quellcode:

var 
  changed: boolean; 
  nav, help1, help2: tListenElement; 
begin 

  changed := False;

  repeat //<<<     
    nav := root; 
    while Assigned(nav) and Assigned(nav^.next) do //<<<
    begin 
      if nav^.name > nav^.next^.name then 
      begin 
        help1 := nav;                     
        nav := nav^.next;                
        help2 := nav^.next; 
        nav^.next := nav^.next^.next; 
        help2^.next := help1; 
        
        changed := True; 
        if help1 = root then
         root := nav;   
      end; 
      nav := nav^.next;                 
    end; 
  until not changed; //<<<

end;

[Chris P]

Danke erstmal, aber ich verstehe immer noch nicht für was der 2. Hilfszeiger "HELP2" gut ist.


Er bekommt doch nur Werte zugewiesen aber mit diesen Werten wird doch gar nichts gemacht.

[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 :mrgreen:

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 ... :wall:

[Chris P]

Danke, werde es gleich mal ausprobieren!

Wenns nicht klappt dann meld ich mich noch ma...

[Chris P]

Das klappt leider gar nicht.

Das Programm hängt sich auf!

Ich verstehe das nicht so ganz mit den Hilfszeigern.

Sie werden untereinander vertauscht aber sonst auch nichts!

Die Variable NAV muss doch nach dem Tauschvoragng wieder einen Werte bekommen.

Nach jedem Schleifendurchlauf verfallen doch die Werte der Hilsvariablen wieder.

Kann mir denn keiner helfen??

[xineohp]

irgendwie dreh ich mich im Kreis :cry:

probiers mal so:

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;

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

wenn's nicht funktioniert häng mal dein Project an, dann probier ich selber mal ein bischen dran rum :cyclops:

[MarkusB]

Hi Jungs!

Der folgende Teil sortiert eine verkettete Liste absteigend:

Delphi-Quellcode:

...

repeat
  changed := false;

  prev_node := nil;
  curr_node := start;

  while assigned(curr_node.next) do
  begin
    next_node := curr_node.next;

    if curr_node.zahl < next_node.zahl then
    begin
      curr_node.next := next_node.next;
      next_node.next := curr_node;

      if prev_node <> nil
      then prev_node.next := next_node;

      if curr_node = start
      then start := next_node;

      changed := true;

      prev_node := next_node;
    end
    else
    begin
      prev_node := curr_node;
      curr_node := curr_node.next;
    end;
  end;
until (not changed) and (curr_node.next = nil);

...

und dazu ein paar Deklarationen:

Delphi-Quellcode:

type
  ...

  PNode = ^TNode;
  TNode = record
            next: PNode;
            zahl: integer;
          end;
  ...

var
  ...
  start: PNode;

  prev_node: PNode;
  curr_node: PNode;
  next_node: PNode;
  ...

Viele Grüße
Markus
:gruebel:

[Chris P]

Endlich klappt es!!!

@MarkusB: Deine Lösung ist endlich die richtige!!! Vielen Dank!!!

@Xineohp: Auch vielen Dank an dich für deine viele Hilfe!!!

:dp: :dp: :dp: :dp: :dp: :dp: :dp: :dp: :dp: :dp: :dp: