in sortierte liste sortiert einfügen

[vsilverlord]

Hallo, ich habe eine sortierte liste ( tsortierteliste), diese hat viele zahlenwerte gespeichert, die alle sortiert sind.
Nun möchte ich eine neue Zahl einfügen, diese soll allerdings richtig einsortiert werden.
Welcher Algorithmus ist dafür wohl am besten geeignet? Heapsort usw. eigenet sich ja eigentlich nur dafür, ganze listen zu sortieren, oder? Welcher algorithmus ist dabei am schnellsten?
gruß

[mkinzler]

Schau die mal TList.Sort() an

[DeddyH]

Ich denke, mit einer binären Suche bekommst Du den Einfüge-Index auch ganz gut.

[vsilverlord]

ok, das problem ist, dass ich nicht nur zahlenwerte einfüge, sondern ganze objekte. Ein attribut dieser Objekte ist dann der zahlenwert, mit dem ich die objekte sortiere, deswegen kann ich tlist.sort() nicht benutzen!
gibts da einen standart algorithmus für binäre suche oder muss ich den neu schreiben? ist das auch für ca. 100000 objekte sinnvoll?
gruß

[DeddyH]

Es gibt ja auch noch TList.CustomSort, da kannst Du selbst bestimmen, nach welchen Kriterien sortiert wird. Und zur binären Suche gibt es IIRC in der DP einige Beispielcodes (u.a. von Luckie).

[nahpets]

Hallo,

für Dein Problem dürfte die binäre Suche die beste Möglichkeit sein, bei 100000 Objekten kommst Du mit ca. 16 oder 17 Vergleichen aus. Weniger geht nicht. (2 hoch 17 = 131072, d. h. bei 131072 Objekten benötigst Du 17 Vergleiche.)

Schau mal bitte unter http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche, dort findest Du auch Beispiele, allerdings nicht für Delphi/Pascal. Sie sollten aber für den Nachbau in Delphi geeignet sein.

[Medium]

Binäre Suche ist sicherlich das schnellste für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann. Je gleichmäßiger die Einträge verteilt sind, desto effektiver wird die darauf basierende Interpolationssuche, die aber bei unerwartet schlecht verteilten Einträgen wiederum zur Laufzeit der linearen Suche (O(n)) verkümmert. Diesem potentiellen Nachteil wird versucht mit der quadratischen Binärsuche zu begegnen, die wiederum eine Weiterentwicklung der Interpolationssuche ist. Und eben letztere würde ich auch versuchen wenn es um ziemlich viele Einträge geht. Bei nur ein paar hundert bis taused ist der Gewinn gegenüber der einfachen binären Suche vermutlich nicht mehr SO ausschlaggebend - je nach Anwendungsfall halt.

Wenn du recht genau weisst, dass deine Einträge z.B. grob quadradtisch oder logarithmisch vorkommen, könntest du durch Anpassung des Teilungsintervalls die einfache binäre Suche auch schon auf ein prima Niveau bekommen, aber das sind dann spezialisierte Anpassungen die ganz von der jeweils einzelnen Liste abhängen.

[hoika]

Hallo,

Das Problem habe ich auch oft.

Die Liste ist ja bereits sortiert !
Ein neues Element soll einsortiert werden soll.

Zur Zeit hänge ich es einfach hinten an und sortiere noch mal (CustomSort).

Die Frage ist:
Finde ich den Index des neuen Elementes auch ohne komplette Neusortierung,
BinSearch findet ja nur einen Wert, aber der Wert steht ja noch nicht drin.
Es müsste also das "genau eins kleiner davor" Element bzw. dessen Index gefunden werden.

Quicksort ist bei schon sortierten Listen besonders schnell,
oder war das das genaue Gegenteil ?


Heiko

[Medium]

Zitat:

Zitat von hoika

Die Frage ist:
Finde ich den Index des neuen Elementes auch ohne komplette Neusortierung,
BinSearch findet ja nur einen Wert, aber der Wert steht ja noch nicht drin.
Es müsste also das "genau eins kleiner davor" Element bzw. dessen Index gefunden werden.

Was die binäre Suche auch erledigt. Dort wo der Algo abbricht wegen nicht gefunden, musst du nur noch einen zusätzlichen Vergleich mit den zwei verbleibenden Elementen machen, und dann weisst du wo du einfügen musst.

Was du machst würde ich glatt als Verbrechen bezeichnen! Quicksort ist zwar als Sortierer auf vorsortierten Listen schnell (nicht das schnellste vermute ich allerdings, aber auch nicht übel), aber auch nur wenn man die Vertauschung als Kostenfunktion her nimmt. Es werden trotzdem noch N*(N-1)/2 Vergleiche gebraucht! Binary search dagegen braucht nur log(N) Vergleiche (im worst-case(!)).
Die Frage am Ende ist ja hier: Brauche ich die Liste nur ein Mal am Ende sortiert, oder brauche ich sie die ganze Zeit sortiert während Einträge kommen und gehen? Im ersten Fall ist ein einmaliger Quicksort nach Befüllen sicherlich die schnellere und bessere Wahl, im zweiten ganz klar eine (gute) Suche. Aber das so zu mischen... kann man auf ein paar zig bis hundert Elementen mal machen aus Faulheit, aber eigentlich gehört das bestraft ;)

Ein wenig versalzen tut man sich das alles aber wenn man diese schmucken Listen auf Array-Basis benutzt, da hier das Einfügen im worst-case (an Index 0) eine O(N) Operation ist, und u.U. gleich noch Speicherallokation + Umkopieren auslöst. Eine Double-Linked-List ist bei sehr vielen Elementen wohl das leichtgewichtigste, was man sich aber durch den Verlust des wahlfreien Zugriffs erkaufen muss. Ab dann muss eben traversiert werden, aber in der Regel geht man ja eh mit Schleifen über Listen - da tut's dann nicht weh statt "Liste[i]" mal "CurrentElement := CurrentElement.Next" zu schreiben.

[hoika]

Hallo,

Zitat:

Was du machst würde ich glatt als Verbrechen bezeichnen!

höhö,

jaja, der gute alte Code.

Bei neuen Code wird es per order by vorsortiert.

TJAAAAAAA, WIR WAREN ALLE MAL JUNG ;)


Ich habe hier nen generischen Suchalg (ähnlich wie TList.CustomSort),
vielleicht erweitere ich den noch um ein SortedInsert.


Heiko