Doppelt verkettete Liste sortieren

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

Delphi-Quellcode:

type
  TDAddress = record
  Value : string;
  PADR   : Pointer;
  end;

Ein DynArray von TDAddress anlegen. Dann in einer Schleife die Liste durchlaufen und den Wert nachdem sortiert werden soll in Value schreiben. In PADR kommt dann die Adresse von dem Element.
Das Array sortieren und anschließend die Liste anpassen.
Liste in das Array schreiben:

Delphi-Quellcode:

var 
    AoTDA : array of TDAddress;
    Runner: Pzeiger;
    i     : integer;
begin
  Runner := Root;
  i      := 0;
  while Runner <> NIL do
  begin
     inc(i);
     Setlength(AoTDA, Length(AoTDA)+1);
     AoTDA[i-1].PADR   := Pointer(Runner);
     AoTDA[i-1].Value  := Runner^.IRGENDWAS;  //Irgendwas ist der Wert nachdem sortiert werden soll 
     Runner := Runner^.next;
  end;
end;

Liste anpassen:

Delphi-Quellcode:

var i : integer;
    Runner : PZeiger;
begin
   Root       := AoTDA[low(AoTDA)].PADR;
   Root^.next := AoTDA[low(AoTDA)+1].PADR;
   Root^.prev := NIL;

   FOR i := low(AoTDA)+1 TO high(AoTDA)-1 DO begin
      Runner        := AoTDA[i].PADR;
      Runner^.prev  := AoTDA[i-1].PADR;
      Runner^.next  := AoTDA[i+1].PADR;
   end;

   Runner       := AoTDA[high(AoTDA)].PADR;
   Runner^.next := NIL;
   Runner^.prev := AoTDA[high(AoTDA)-1].PADR;
end;

Die 2 Variante benutze ich im moment, allerdings habe ich gehört das man das so nicht machen darf.
Hatte jemand mit sowas schonmal Erfahrungen gemacht? Gibt es eine Muster-, Standartlösung?

[DelphiDeveloper]

Ich sehe an deinem Code noch nicht die doppelverkettung aber mit PREV und NEXT kann ich schon erahnen wie
es gemacht ist.

Schau dir in Delphi doch mal die TList an, hier ein kleines Beispiel wie man darin records/objekte einhaengen kann:
Die Sortiertung ist dann ein Kinderspiel für dich:

Hier die Sourceb die ich gerade auf die schnelle zusammengeklickt habe:

Delphi-Quellcode:

{-----------------------------------------------------------------------------
 Author:    DelphiDeveloper  05.02.22
 Purpose:   Sort with TList
-----------------------------------------------------------------------------}
unit Unit1;
interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;

type

  TDAddress = class
    SValue: string;
    IValue: integer;
    PADR: Pointer;
  end;

  TForm1 = class(TForm)
    BtnCreateTheList: TButton;
    BtnShowList: TButton;
    ListBox1: TListBox;
    RGrpSort: TRadioGroup;
    BtnSort: TButton;
    procedure BtnCreateTheListClick(Sender: TObject);
    procedure BtnShowListClick(Sender: TObject);
    procedure BtnSortClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
    myList: Tlist;
    procedure ClearList;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.BtnCreateTheListClick(Sender: TObject);
var aAdrObj: TDAddress;
  I: integer;
begin
  myList := TList.create;
  // fuelle Liste mit beispielwerten
  for i := 1 to 5 do
  begin
    aAdrObj := TDAddress.Create;
    aAdrObj.SValue := chr(random(20) + 65);
    aAdrObj.IValue := random(10);
    MyList.Add(aAdrObj);
  end;
end;

procedure TForm1.ClearList;
var I: integer;
begin
   // erst die Objekte freigeben
  if assigned(MyList) then
  begin
    for i := 0 to myList.Count - 1 do
      if MyList.Items[i] <> nil then
        TDAddress(myList.Items[i]).Free;
    //und jetzt die Liste
    MyList.Clear;
  end;
end;

procedure TForm1.BtnShowListClick(Sender: TObject);
var i: integer;
begin
  // nur um anzuzeigen was in der Liste steht
  ListBox1.Clear;
  for i := 0 to myList.Count - 1 do
  begin
    ListBox1.Items.Add(Inttostr(TDAddress(myList[i]).IValue) +
      ' ' + TDAddress(myList[i]).SValue);
  end;
end;

function SortierenString(item1,item2:pointer):integer;
begin
  // intern wird quicksort algo verwendet siehe OH
  // sortierung von strings
  result:=CompareText( TDAddress(Item1).SValue, (TDAddress(Item2).SValue));
end;

function SortierenInteger(item1,item2:pointer):integer;
begin
   // intern wird quicksort algo verwendet siehe OH
  // sortierung von integerwerten
  result:=( TDAddress(Item1).iValue - (TDAddress(Item2).iValue));
end;

procedure TForm1.BtnSortClick(Sender: TObject);
begin
   case  RGrpSort.ItemIndex of
     0: MyList.Sort( SortierenInteger);
     1: MyList.Sort( SortierenString);
   end;
   // neu anzeigen
   BtnShowList.OnClick(sender);
end;

end.

[Chewie]

Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!

[IngoD7]

Zitat von Chewie:

Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!

Stimmt. Wo wurde denn was anderes behauptet?

[Chewie]

Naja, das Thema sind doppelt verkettete Listen, und der Vorredner brachte heri TList ins Spiel.

[IngoD7]

Zitat von Chewie:

und der Vorredner brachte heri TList ins Spiel.

Ja schon, aber (wenn ich es richtig verstanden habe) als Alternative zur verketteten Liste.

[Chewie]

Hm, wie auch immer. Man kanns auf jeden Fall nie oft genug sagen

[Niko]

Hi

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.

Genau deshalb ist Quicksort für eine verkettete Liste nicht besonders gut geeignet. Das schnellste Sortierverfahren für Listen dürfte Mergesort sein (benötigt keinen direkten Zugriff auf die Elemente).

[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];

[Robert Marquardt]

Der einfachste Weg ist es ein Array von Zeigern auf die Daten zu erzeugen und dann dieses Array mit QuickSort oder HeapSort zu sortieren.
Das funktioniert wenn die Daten selbst als Zeiger im Verkettungsknoten gespeichert sind.
Danach spielt man die Zeiger einfach wieder in die Liste ein.

Natuerlich hat dieses Verfahren eine limitation, naemlich der zusaetzliche Platzaufwand fuer das Array.