Was ist günstiger? Array oder verkettete Liste??
-
nman schrieb:
Hm, Binärsuche in einem Sortieralgorithmus? Warum klingelt da irgendwas bei mir?
Wo ist das Problem? Gesucht wird in der sortierten Teilsequenz. Ich glaube nur nicht, dass das sonderlich viel bringt, weil das Einfügen immer noch linear ist und viel teurer als das suchen.
-
rapso schrieb:
ich glaube ein ArrayOfPointers is grundsaetzlich nie groesser als "die prev/next-Zeiger" einer gleich langen liste.
Bleibt immer noch der Aufwand, Array-Elemente zu kopieren (selbst wenn du die Sequenz "indirekt" sortierst, mußt du am Ende die Array-Elemente umkopieren, um damit weiterarbeiten zu können).
@nman: Was sollte dagegen sprechen? Der vordere Bereich bei InsertSort ist bereits geordnet, also kann man die Einfügeposition auch mit Binärsuche ermitteln.