Doppelt verkettete Liste sortieren

[Mr.P-Funk]

@ DelphiDeveloper
Der Vorschlag mit TList zu arbeiten, erspart sicher viel Zeit, ist aber nicht ganz das was ich wollte.
Trotzdem THX für die Idee.

@ Niko
MergeSort kenne ich noch nicht... leider :(
Werde mir das aber mal ansehen.

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.
Das Array lässt man dann sortieren und "verbiegt" seine Liste neu (Die Daten davon liegen ja noch im Speicher).

Wenn ich das richtig verstanden habe, würdest du alle Infos die in der Kette stehen auch in das DynArray schreiben. Aber dann würde ein Dreickstausch doch sehr lange dauern, wenn das record aus mehr Feldern bestehen würde...
Oder habe ich das jetzt falsch verstanden? :gruebel:


Ich habe mal ein kleines Beispielprogramm erstellt.
Allerdings raten mir viele Leute davon ab, das so zu machen. Es wäre zu unsicher...
Könnt ja mal reinschauen.

Großes THX an alle! :hello:

cya
MR.P-Funk

[negaH]

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen. Man kann dies noch beschleunigen indem man zur ListB ein Array mit Ln2(ListA.Count) Pointern benutzt. In diesem Array wird ein Zeiger auf das jeweils ListB.Count/Ln2(ListA.Count) Element/Node gespeichert. Beim Enfügen einer Neuen Node wird nun dieses Array per QuickFind durchsucht um die Anfangsnode ab der die Liste itertiert werden muß zu finden. Dies beschleunigt ungemein das sortierte Einfügen in deine ListeB.
Das Zusatzarray wird von Anfang an auf ListA.Count Elemente initialisiert und dann deren enthaltene Pointer nur succesive nach dem Einfügen/Umkopieren der Node geupdatet. Bei diesem Update kann man sich weiter beschränken indem man nur die beiden "Rand" Nodes in diesem Array korregiert.

Hm, ich glaube nicht das ich das verständlich rübergebracht habe

Gruß Hagen

[shmia]

Zitat von Mr.P-Funk:

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.

Da hast du nicht genau hingeschaut.
Das Array aus meinem Vorschlag enthält nur Zeiger (Datentyp PSortItem)
Der typisierte Pointer vereinfacht das Programmieren...

[Hansa]

Zitat von negaH:

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen....Hm, ich glaube nicht das ich das verständlich rübergebracht habe Gruß Hagen

Hehe, ich verstehe das auch nicht. 8) Ich vermute mal, er will das sagen, was man machen sollte : die Liste direkt sortiert aufzubauen und basta. Dann entfällt der Rest sowieso. Muß die Liste unbedingt komplett anders umsortiert werden, tja dann eben wirklich unter dem neuen Sortierkriterium neu aufbauen.

[negaH]

@Hansa, stop mal, will er die Liste umsortieren oder will er einen sortierten Index für die Liste aufbauen ohne die Liste physikalsich umzusortieren ?

Ich war der Meinung das er die Liste umsortieren will. Da er eh schon mit Verketteten Nodes/Elementen arbeitet ist es auch kein Problem sehr schnelle Nodes aus einer Liste zu erntfernen und in eine andere Liste sortiert einzufügen. Dies kostest erstmal keinen zusätzlichen Speicher. Allerdings muß er beim Einfügen einer Node in die neue und sortierte Liste im ungünstigen Falle immer diese Node mit allen Nodes in der Zielliste vergleichen. Dies ist sehr ineffizient. Man könnte nun ein komplettes Array[] of PNode aufbauen das so viele Zeiger wie Nodes in der Liste enthält. Dies kostet Speicher, lässt sich aber per QuickSort einfach und schnell sortieren, wäre vergleichbar mit einem externen Index und kostet im Grunde sehr viele Speicherkopieroperation während der Sortierei.

Ein Kompromiss ist nun eine Lösung die beide primären Varianten vereint, sprich Umsortieren in neue List und dabei ein sehr kurzes Indexarray für die Suche der Einsortierposition der Node.

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Somit wäre mein Vorschlag leicht langsammer beim Suchen der richtigen Einfügeposition, allerdings wird dies durch die wesentlich erhöhten Speicheroperationen bei den anderen Methoden weitestgehend kompensiert. Denn Speicherkopierungen sind wesentlich langsammer auf modernen CPU's also nur readonly durch eine verkettete Liste durchzuiterieren.

Falls das Sortieren der Liste wirklich enorm schnell gehen muß dann kann man das durch eine Erweiterung der Nodes erreichen. Die Nodes selber sind als verkettete Liste linear untereinander verknüpft. Aber gleichzeitig sind sie auch als Binärer Baum, zb. ein AVL oder Red Black Tree aufgebaut. Die Nodes müssten dann nicht mehr doppelverlinkt werden, aber zusätlich benötigen sie mindesten zwei weitere Zeiger -> Left,Right.
Beschränkt sich das Sortieren aber nur auf das Einfügen in einen solchen Tree dann kann man die Left,Right Zeiger später als Prev,Next Pointer für die verlinkte Liste benutzen. Während des Aufbauens des Baumes entsteht also ein ausbalancierter binärer Baum (RB, AVL). Nachdem man alle Nodes so eingefügt hat, kann man mit einer Rekursiven Funktion die den Baum sequetiell alphabethisch abarbeitet, neu zu einer normalen doppeltverlinkten Liste ummodscheln Klar, einmal in eine Liste umgemodschelt kann man keine neuen Nodes mehr sortiert als Baum einfügen.
D.h. temporär beim Umsortieren werden die Nodes statt in einer linearen Liste in einen binären Baum eingearbeitet, aus den Prev,Next Zeigern werden die Left,Right Zeiger für den AVL/RB Tree. Nachdem man alle Nodes so binär umkopiert hat wird der Baum neu verlinkt so das eine Liste entsteht.

Dieses Verfahren ist Ln2(List.Count) schnell, asymptotisch schneller als QuickSort !! benötigt keinen zusätzlichen Speicher und keine Kopieroperationen ausser dem Umbiegen der Zeiger. Allerdings ist es komplex und nicht einfach zu coden.

Gruß Hagen

[mleyen]

Zitat von negaH:

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Ich weiß der Thread ist schon uralt, aber für mich gerade aktuell da ich auch eine eigene spezielle Liste bastle.
Ziemlich interessant wie du den Ramverbrauch der CPUlast gegenüberstellst. (Ich war immer der Meinung, dass das bei Such/Sortierverfahren, aufgrund des dynamischen Inhalts, nahezu nicht geht)
Aber was tut bitte "Ln2()"?

[Sherlock]

Ins blaue geraten ist das der Logarithmus mit Basis 2.

Sherlock

[Gollum]

Hallo,

wenn ich den Link aus dem Thread von Hansa anklicke komme ich auf eine Seite, die vBulletin-Systemmitteilung heißt und mir etwas von mangelden Rechten erzählt.
Ist dieser Link so geheim, dass ich ihn nicht anklicken darf oder ist dies ein Bug?

[xZise]

Moin,
wobei Ln2() auch irgendein anderer Logarithmus sein kann. O(LnX()) = O(LnY())

Und wegen Hansas Post: Entweder er liegt irgendwo, wo der Otto Normal Benutzer nicht hin darf, oder bei der Umstellung auf die DP20XX ist was schief gelaufen.

MfG
Fabian

[Mr.P-Funk]

@ Shima
Upps zu schnell gelesen...
Aber die einen typisierten Zeiger zu nehmen ist gut, warum bin ich da nicht selber drauf gekommen ...
Damit ist der Aufwand wohl echt geringer.

@ negaH
Das hört sich ja interessant an, aber ich hatte schon Probs das überhaupt zu verstehen, nen Code kann ich mir nur schwer vorstellen...
Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??

Ich erkläre den Thread als geschlossen; meine Fragen wurden beantwortet
THX @ all