long array sortieren
-
Hi zusammen,
ich lese eine Datei ein und konvertiere nach bestimmten Schemen die Daten in long Werte und schreibe sie in ein long array. Bei Berechnungen ist mir nun aufgefallen, dass ich oft sortierte Daten brauch sprich an der Stelle [0] steht mein minWert und an der Stelle [n] steht mein MaxWert. wie realisiere ich soetwas, so dass ich performanztechnisch einigermaßen ordentlich bleib? Der Hintergrund ich hab Taktzeiten von ca 20 Sekunden und in der Zeit muss ich viele viele Berechnungen machen und DFTs etc drüber laufen lassen.
Vielen Dank schon im Voraus für eure Hilfe
-
Sortierverfahren gibts wie Sand am mehr^^
Wieviel Daten können denn in so einem Array stehen? Je nach Menge sind verschiedene Verfahren geeignet.
-
Ich würde an dieser Stelle den Heap- oder Quicksort vorschlagen. Beide arbeiten mit einer Komplexität von O(n*log(n)). Der Quicksort läuft im worst case allerdings mit einer Komplexität von O(n²).
-
naja Momentan sind es ca 35000 Werte. Ich nehm auch an, dass das so der Durchschnitt bleiben wird. Es sollte allerdings auch mit wesentlich mehreren Daten laufen. (Da ist dann die Performance egal)
Wie realisiere ich denn solch ein Verfahren
-
schau doch mal nach Bubble Sort, straight insertion sort etc!
-
Wow hab was nettes gefunden, wenn ich damit nicht klar komm werd ich bei euch noch mal betteln kommen
was haltet ihr vom Quicksort bei 35000 Werten??
-
Warum benutzt du nicht die Standardalgos? std::sort baut auf Quicksort auf, es gibt auch noch andere in der STL verankert.
-
Polofreak schrieb:
was haltet ihr vom Quicksort bei 35000 Werten??
naja, dein rechner braucht dafür ungefähr eine millisekunde, wenn die daten vorher echt durcheinander waren. ist dir das zu langsam?
nimm lieber std::sort, das braucht immer ungefähr eine millisekunde.