Doppelt verkettete Liste sortieren

[shmia]

Zitat von Mr.P-Funk:

Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.

Mit einem zusätzlichen Speicheraufwand von 1 Zeiger pro Element kann man ein indirektes Sortieren durchführen:

Delphi-Quellcode:

type
   PSortItem =  ^TSortItem;
   // die Grundstruktur deiner doppelt verketteten Liste
   TSortItem = Record
      data:string;
      Prev : PSortItem;
      Next : PSortItem;
   end;

var 
   // Hilfsarray zum Sortieren
   SortArray : array of PSortItem;

Ich gehe jetzt davon aus, dass deine doppelt verkettete Liste komplett aufgebaut ist.
Der nächste Schritt ist nun das Hilfsarray zu dimensionieren.
Dazu wird die Anzahl der Elemente benötigt (entweder schon bekannt oder man muss die Liste durchzählen):
   SetLength(SortArray, AnzahlElemente); Jetzt wird das Array bestückt:

Delphi-Quellcode:

runner := FirstElement
for i:=0 to AnzahlElemente-1 do
begin
   SortArray[i] := runner;
   runner := runner.Next;
end;

Jetzt ist der double-linked List ein Array übergestülpt.
Beim Sortieren wird nun über das Array SortArray gearbeitet und innerhalb des Arrays werden Zeiger vertauscht.
Die Verkettungen innerhalb der double linked List bleiben völlig unberücksichtigt.
Nach dem Sortieren enhält das Array die Zeiger auf die Elemente in sortierter Form.
Jetzt werden alle Verkettungen der double-linked List quasi weggeschmissen und mit Hilfe
des SortArray neu aufgebaut:

Delphi-Quellcode:

Head := SortArray[0]; // Kopf der Liste
// gesonderte Behandlung für Anfangselement
SortArray[0]^.Prev := nil;
SortArray[0]^.Next := SortArray[1];
for i := 1 to AnzahlElemente-2 do
begin
   SortArray[i]^.Prev := SortArray[i-1];
   SortArray[i]^.Next := SortArray[i+1];
end;
// gesonderte Behandlung für letztes element
SortArray[AnzahlElemente-1]^.Prev := SortArray[AnzahlElemente-2];
SortArray[AnzahlElemente-1]^.Next := nil;
Tail := SortArray[AnzahlElemente-1];