Problem beim Sortieren von Arrays

Hallo,

Ich habe eine Arraystruktur ( vector) die ca. so ausehen könnte:

a 5
b 3
c 1
d 4
e 2

--

Die möchte ich nun nach Zahlen aufsteigend Sortieren, sodass die anderen weret mitsortiert werden. Problem ist: Es können über 30000 Elemente in dieser Array sein.
Ich habe es mit Bubblesort probiert jedoch war das Ergebniss erst nach ca 100 Sekudnen zu begutachten. Mit shellsort kamen komischerweise falsche werte raus. Und Quicksort hat erst garnicht funktioniert.

Kann mir da jemand helfen?

MfG Tetsu

Jansen

Wie soll dir jemand helfen, wenn du nicht zeigst, was du genau versucht hast?

CStoll

Wenn die Werte zusammenbleiben sollen, mußt du sie auch gemeinsam speichern (z.B. in einem vector<pair<char,int> >). Und dann solltest du dir mal den sort()-Algorithmus aus der STL ansehen, anstatt dir etwas eigenes zu bauen (gerade bei so großen Datenmengen sind O(n²) Algorithmen wie Bubblesort eher unbrauchbar.

Jansen schrieb:

Wie soll dir jemand helfen, wenn du nicht zeigst, was du genau versucht hast?

Ich will deine Array ca. so sortieren:

von

a 5
b 3
c 1
d 4
e 2

nach

c 1
e 2
b 3
d 4
a 5

Ich fand nur die funktion qsort, weiß aber nicht wie ich sie anwenden soll.

CStoll

besser gar nicht (wenn du vector sagst, tippe ich auf ein C++ Programm - und dort ist sort() die erste Wahl - typsicher und wesentlich flexibler als qsort)

typedef pair<char,int> data_t;

//Vergleichsfunktion:
bool sort_second(const data_t& l,const data_t& r)
{ return l.second<r.second; }

vector<data_t> my_data;
...
sort(my_data.begin(),my_data.end(),sort_second);

Ah danke nun geht es.

Wie bitte funktioniert dieser Algo das er in der Lage ist über 30000 bis 50000 Einträge unter 1 Sekunde zu ordnen?

Naja trodzdem vielen dank.

MfG Tetsu

CStoll

Ist "30000 Einträge in unter 1 Sekunde" ein gemessener Wert? Dann hast du vermutlich einen recht schnellen Rechner. sort() verwendet intern idR QuickSort(), das hat eine durchschnittliche Laufzeit von O(n log n) - und ist eins der schnellstmöglichen Verfahren, um per "compare-and-swap" zu sortieren (schnellere Verfahren verwenden andere Ansätze, siehe z.B. BucketSort).