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?!
EDIT: hab übersehen, das du das schon tust, sorry.

[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 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
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?