Binärer Baum vs. sortierte verkettete Liste
-
wenn ich aber k elemente in eine n-elementige liste einfügen will, hab ich als aufwand doch k*n. und dann würd sich merge doch schon wieder nicht lohnen, bei kleinem k.
-
bei kleinen werten isses eh egal. für kleine n ist es auch wurscht ob liste, array oder baum.
-
hansile schrieb:
Aber nehmen wir mal zus. an, dass der Wrapper ein paar Meta-Infos, wie Zeiger auf Element an 1/2*size, ...
Wenns du den Gedanken jetzt konkretisierst dann hast du einen Binär Baum.
Bashar schrieb:
Achso. Ansonsten gäbs da ja z.B. Merge Sort.
Um Merge Sort aber in O(n*log(n)) zu realisieren brauchst du einen zweiten Puffer. Dann kannst du aber auch gleich deine Liste in ein Array kopieren, XY Sort drauf loslassen und dann wieder in die Liste zurückkopieren.
Merge Sort kann man zwar auch ohne extra Puffer realisieren allerdings ist das dann nicht mehr O(n*log(n)). Ich bin mir jetzt nicht sicher wie das Verfahren genau ist aber im Sedgewick steht was zum Thema drin.
Desweiteren sehe ich nicht wie man Teile & Herrsche auf einer verketteten Liste machen sollte ohne noch mal zusätzlichen Speicher zu brauchen.
Heap Sort geht soweit ich das sehe auch nicht auf einer verketteten Liste.
Eigentlich eine interessante Frage : Gibt es ein Sortierverfahren mit einer Zeitkomplexität in O(n*log(n)) welches einfach verkettete Listen allgemeiner Werte sortiert ohne dabei zusätzlichen Speicher zu verwenden? ("allgemeiner Werte" damit keiner mit Bucket Sort ankommt und einfach verkettet da man bei doppelt verketteten Listen diese wahrscheinlich in einen binär Baum überführen kann und dann wieder zurück. Mit zwei Zeigern pro Knoten kann man ja ganz gut einen Baum basteln.)
-
@Ben04:
MergeSort ist doch hervorragend dafuer geeignet, verkettete Listen inplace zu sortieren? (und das sehr wohl in O(n log n)
Aber warum reden wir hier eigentlich ueber Mergesort? Ich wollt mit meinem Kommentar nur drauf hinweisen dass das Einfuegen von neuen Elementen in die Liste mit der Forderung, die Liste zu jedem Zeitpunkt geordnet zu halten, auf Insertionsort hinauslaeuft. Und das ist auf Dauer nicht sehr effizient.
-
Zumindest wenn man von einer zufälligen gleichverteilten Eingabe ausgehen kann man listen auch mit quicksort in O(n log n) Zeit inplace sortieren. Mit Listen in-place arbeiten ist sowieso viel einfacher als mit Arrays.
-
Blue-Tiger schrieb:
@Ben04:
MergeSort ist doch hervorragend dafuer geeignet, verkettete Listen inplace zu sortieren? (und das sehr wohl in O(n log n)Ein O(n log n) Merge Sort braucht ein O(n) Merge. Wie kriegst du das zustande?
Mit dem Quick Sort scheint es in der Tat zu gehen. Die Partition liefert ja nebenbei auch die Elemente an deren Grenze man "scheiden" muss. Von daher ist es nicht schlimm, dass man nicht mal einfach die Mitte bestimmen kann.
-
Ben04 schrieb:
Blue-Tiger schrieb:
@Ben04:
MergeSort ist doch hervorragend dafuer geeignet, verkettete Listen inplace zu sortieren? (und das sehr wohl in O(n log n)Ein O(n log n) Merge Sort braucht ein O(n) Merge. Wie kriegst du das zustande?
Wo siehst du genau das Problem?
Merge-Sort geht etwa so: Bis zur Mitte der Liste laufen, dann linken Teil mit merge-sort sortieren, rechten teil mit merge-sort sortieren, dann mergen.
mergen geht doch prima in-place, weil man ja nur ein paar zeiger umhängen muß.
ich hab also eine liste result, und die listen a und b und hänge die Elemente nach und nach von a bzw. b nach result um. Das verbraucht zu jeder Zeit nur konstanten zusätzlichen Speicher, ist also in-place.
-
Wo siehst du genau das Problem?
kA, stand grad irgendwie auf dem Schlauch...
-
<a href="http://www.mapwatches.com">swiss replica rolex</a> are today a style statement, preferred by celebrities worldwide. The history are more than 100 years, watchmaker Omega has been creating masterpieces in the area of luxury brand watches.
-
The replica watches for men, whose inspiration was found in the historical model from 1925. Patek Philippe are known for creating high quality, high desire watches.
-
nett gemeinter vorschlag, aber es sollte zumindest ein bischen authentisch wirken
