@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