Spezieller Sortieralgorithmus

X

Xo-mate

Erfahrenes Mitglied
Hallo
Der Titel hört sich vielleicht etwas flach an, aber was solls.

Ich bin auf der Suche nach einem Sortieralgorithmus. OK - Quicksort - klar. Oder doch nicht? - warum?

1.
Nun, ich habe bereits eine vorsortierte Liste und will nun einen weiteren Eintrag einfügen.
Dafür muss ich ja nicht jedes mal die ganze Liste sortieren...

Welcher Sortieralgorithmus - wenn überhaupt ein "klassischer" Sortieralorithmus - kommt da am ehesten in Frage?

2.
Außerdem hab ich eine weitere Liste, die zwar vorsortiert ist, wo sich aber einige "Querschläger" drin aufhalten. Hier muss, denke ich, ein klassischer Sortieralorithmus ran - aber welcher?

Ich habe bereits diese hier gefunden, wobei bei einer unsortierten Liste die letzten 4 alle etwa gleich gut sind, wobei der Selectionsort durch wenig arrayzugriffe ausgezeichnet ist, Bubblesort ist hier nur mal zur Vollständigkeit aufgeführt ;):
Bubblesort, Insertsort, Selectionsort, Quicksort, Mergesort, Heapsort
 
Xo-mate hat gesagt.:
1.
Nun, ich habe bereits eine vorsortierte Liste und will nun einen weiteren Eintrag einfügen.
Dafür muss ich ja nicht jedes mal die ganze Liste sortieren...

Welcher Sortieralgorithmus - wenn überhaupt ein "klassischer" Sortieralorithmus - kommt da am ehesten in Frage?
Zum Vergrößern anklicken....
Binäre Suche nach der richtigen Position und dann dort einfügen. Oder gleich eine Suchstruktur (Binärbaum, B-Baum) für die Liste halten und diese dann zur Suche der Einfügeposition verwenden.

Xo-mate hat gesagt.:
2.
Außerdem hab ich eine weitere Liste, die zwar vorsortiert ist, wo sich aber einige "Querschläger" drin aufhalten. Hier muss, denke ich, ein klassischer Sortieralorithmus ran - aber welcher?
Zum Vergrößern anklicken....
Quicksort hat bei ungünstiger Wahl des Pivot-Elements bei (fast vollständig) vorsortierten Listen den Nachteil, dass die Laufzeit dann annähernd quadratisch wird. Bei Heapsort tritt dies bspw. nicht auf.

Grüße,
Matthias
 
Hi.
Xo-mate hat gesagt.:
1.
Nun, ich habe bereits eine vorsortierte Liste und will nun einen weiteren Eintrag einfügen.
Dafür muss ich ja nicht jedes mal die ganze Liste sortieren...
Zum Vergrößern anklicken....
Ein Element in eine sortierte Sequenz einzufügen, so dass die Sequenz hinterher noch sortiert ist, ist trivial. Dafür braucht man keinen Sortieralgorithmus - man fügt einfach an der richtigen Stelle ein.

Xo-mate hat gesagt.:
2.
Außerdem hab ich eine weitere Liste, die zwar vorsortiert ist, wo sich aber einige "Querschläger" drin aufhalten. Hier muss, denke ich, ein klassischer Sortieralorithmus ran - aber welcher?
Zum Vergrößern anklicken....
Um wieviel Elemente insgesamt geht es denn? Oder ist das nur eine allgemeine Frage? Es dürfte klar sein, da nicht unbedingt Quick- oder Heapsort zu nehmen. Ein einfaches SelectionSort sollte ausreichen.

Gruß
 
Hi.
Matthias Reitinger hat gesagt.:
Kannst du das bitte näher erläutern? Für mich ist das nämlich nicht so ganz klar.
Zum Vergrößern anklicken....
Und ich dachte du würdest wissen was gemeint ist... ;) Ich stand wohl aber etwas neben mir, denn ich wollte eigentlich InsertionSort vorschlagen und nicht SelectionSort. Sorry. :-(

Wenn da wirklich nur ein paar Elemente nicht an der richtigen Position sind und es sich dazu noch wirklich um eine (einfach/doppelt verkettete) Liste handelt, ist es den Verwaltungs-Aufwand für Quick- und Heapsort einfach nicht wert. Ein simpler InsertionSort Algorithmus ist da schneller - und nicht zuletzt auch schneller implementiert.

Quicksort benötigt (etwas) zusätzlichen Speicher und hat im schlechtesten Fall abhängig von der Wahl des Pivotelements eine Laufzeit von O(n^2). Dazu kommt das der Zugriff bei einer Liste nicht wahlfrei erfolgen kann und das umhängen von Elementen der Liste relativ "teuer" ist.

Gruß
 
Du brauchst ersteinmal die richtige Speicherstruktur. Es empfiehlt sich eine (doppelt) verkettete Liste oder ein B-Baum. Wikipedia hilft dir hier weiter. Dann geht das Einfuegen in O(ln n).
 
Es ist eine Liste mit mehreren tausend Einträgen. (z.B. 10.000)
gut, das mit dem Einfügen ist nicht so das Ding - hatte gedacht, dass hier vielleicht noch irgendwas gutes kommen könnte ;)

Beim zweiten ändern sich zu einem Zeitpunkt etwa 1.000 bis 3.000 Einträge. Nach dem Ändern müsste die Liste dann, wenn ich euch jetzt richtig verstanden hab, mit InsertSort? Beim Insertsort hab ich allerdings anhand dieses Java-Progs http://madpenguin.de/public/apps/sortIt/sortIt.jnlp ehr gesehen, dass es anhand der Arrayzugriffe und Vergleiche nicht so optimal ist?!
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück