in sortierte liste sortiert einfügen

[Medium]

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.