quicksort / iterativ suchen
-
hallo,
ich weiß es ist ne seltsame frage, aber im grunde meines herzens bin ich mir nicht sicher....
sagen wir ich habe ein array mit DWORDs(in einer structure!!!etwa 40 byte) die ich jedes mal wenn ich wieder eine solche structure einfügen will, wieder vergleichen muss ob ich bereits das element eingefügt habe.
ich programmiere ansi-c also habe ich keinen tollen speicher-management-funktionen zur Verfügung.
nun meine frage ist es besser das array unsortiert zulassen, und einfach iterativ darin zu suchen, ob ich ein element bereits eingetragen habe, oder jedes mal das array mit quicksort zu sortieren beim einfügen, und dann wenn wieder ein element eingefügt werdenn soll, mit binärer suche schauen ob es bereits vorhanden ist ?
sorry für diese einfache frage ...
-
füge das neue ELement doch gleich an der richtigen Stelle in dem Array
ein. Dann hälst du immer ein sortiertes Array.Dann brauchst du für Einfügen O(logn) und zum Suchen auch O(logn)
-
hm, wenn ich nun ein Array mit n Elementen habe und irgendwo in der Mitte etwas einfüge, dann laufe ich von Anfang bis zu der Stelle, wo ich einfügen möchte, dann laufe ich von dieser Stelle bis zum Ende, um die nachfolgenden Elemente zu verschieben, dann schreibe ich das Element an die richtige Stelle. D.h. ich durchlaufe jedes mal das komplette Array: O(n) (selbst im best-case).
Wenn es auf Geschwindigkeit ankommt und es nicht unbedingt ein Array sein muss, dann würde ich einen Binärbaum nehmen, am besten einen AVL-Baum, der sich beim Einfügen und Löschen immer selbst ausgleicht, da hast Du tatsächlich selbst im worst-case O(log n). Wenn Du das Array unbedingt brauchst aber nicht sortiert und es nicht so auf Speicher ankommt, dann kannst Du parallel ein Array mitlaufen lassen und das jeweils neue Element hinten anfügen, im Baum speicherst Du dann zusätzlich den Index im Array, wüsste zwar nicht wofür man das so gebrauchen kann, aber so hast Du eine Referenz vom Baum zum Array. Falls Du das Array nur hin und wieder mal brauchst (ka wofür), dann kannst Du Dir ja eine Funktion schreiben, die dir aus dem Baum ein sortiertes Array erstellt.
Aber wenn es auf Geschwindigkeit ankommt und Du nicht unbedingt ein Array brauchst, dann nimm den Baum.
// Falls ich mich irre, dann belehrt mich bitte eines besseren.
-
verkettete listen? hat ordnungswächter sicher gemeint.
ein struct type und ein paar hilfreiche funktionen und das klappt.
-
liste macht keinen sinn, denn dann ist es mit der binären suche nicht so toll ....1!
-
kennt jemand eine schnelle implementierung für "binary insertion"??
am besten mit ner compare function, und memmove so das sie mit allen daten typen zurecht kommt
-
und was ist mit einer indexliste? du hast ein array mit pointern und musst beim einfügen nur das pointer array manipulieren. konstanter lesezugriff, schreiben auch, einfügen/löschen sollte dank memcpy/memmove auch nicht tragisch sein.