Bubble vs. Quick - Sort

[Jabber]

Hallo zusammen,

ich habe eine Frage bezüglich Bublle bzw. Quick Sort. Wie könnte ich eine dieser Sortierverfahren in meinem kleinen Beispielprg. integrieren?

Welches Sort ist eurer Meinung das Beste?

1: // Aufzählung - Arrays

2: #include <iostream.h>

3:

4: int main()

5: {

6: int myArray[5];

7: int i;

8: for (i=0; i<5; i++) // 0-4

9: {

10: cout << "Wert fuer myArray[" << i << "]: ";

11: cin >> myArray;

12: }

13: for (i = 0; i<5; i++)

14: cout << i << ": " << myArray << "\n";

15: return 0;

16: }

Danke für eure Hilfe !

[Orffi]

Du weißt aber schon, wie man Bubble Sort und Quick Sort in C++ programmiert, oder? Wenn dem so ist, dann sollte es ja nicht mehr so schwer sein, die Verfahren einzubinden.

Die Frage, welcher Sortieralgorithmus am besten ist, läßt sich so generell nicht sagen. Aber wenn Du zum Beispiel nur 20 Einträge sortieren willst, dann kann man auch ganz gut mit einem Bubble Sort leben. Es lohnt sich manchmal eben nicht, irre viel Zeit und Komplexität in ein Sortierverfahren zu stopfen, das selten aufgerufen wird und keine großen Daten sortieren muß.

HTH

Jan

[nic_power]

Das einfachste duerfte sein, die entsprechende qsort() Routine aus der C-Bibliothek mit einzubinden ("man qsort").

Nic

[yamato]

generell kann man sagen, dass quick sort eigentlich das schnellste sortierverfahren ist, das existiert.

wie gesagt: generell.

aus diesem grund ist es auch in der c std lib gelandet.

welches verfahren für einen selbst das bessere ist, kann man ganz leicht rausfinden, in dem man die zeit misst, die der sortier-algorithmus braucht. (unter win32: timeGetTime).

sicherlich kann man sich einige arbeit sparen, wenn man von vornherein weiss, dass man nur 20 bytes sortieren. bubble sort ist da schnell runtergetippt.

ich würde eine sortier-funktion folgendermassen aussehen lassen (funktionsname natürlich nur als beispiel):

void HeapSort (void* InputBuffer, void* OutputBuffer, long BufferSize)

[Orffi]

"generell kann man sagen, dass quick sort eigentlich das schnellste sortierverfahren ist, das existiert. "

Und das kann man genau nicht sagen. Das von Dir schon erwähnte Heapsort ist im worst-case-Fall schneller als Quicksort. Quicksort hat im worst-case eine Laufzeit von O(n²) und im average-case O(n log n). Heapsort hat in beiden Fällen die Laufzeit O(n log n)!

Es geht aber noch schneller: Wenn bestimmte Bedingungen erfüllt sind, kann ich auch in O(n) sortieren. Siehe Radix/BucketSort.

Jan

[yamato]

ich weiss ich weiss.

über sowas kann man ein ganzes buch schreiben.

wenn man nicht genau weiss, oder nicht genau wissen will, wie die unsortierten daten aussehen und eine konstante sortier-zeit braucht, dann nimmt man heap sort.

aber in den MEISTEN fällen ist quicksort nen tick schneller.

zumindest ist es besser als bubblesort, und das war ja die ursprüngliche frage.

[Crush]

Mir persönlich scheint der Radix-Sort am schnellsten zu sein, sofern die Datenmenge und der Sortierbereich entsprechend begrenzt ist.

[nic_power]

Der optimale Sortieralgorithmus ist von den Eingabedaten abhaengig. Kann man bestimmte Annahmen treffen, so lassen sich Verfahren einsetzen, die effizienter als ein QuickSort sind. Fuer "Ottonormalprogrammierer" reiche ein Quicksort in der Regel aus.

@yamato: Der Prototyp macht wenig Sinn, wonach willst Du denn da sortieren?

void HeapSort (void* InputBuffer, void* OutputBuffer, long BufferSize)

Die Funktion muss zumindest wissen, wie die einzelnen Elemente aussehen und welche Sortierfunktion zu verwenden ist. Schau Dir einfach mal den Prototyp fuer "qsort" aus der libc an.

Nic

[Jabber]

Vielen Dank erst mal.

Das Problem bei mir ist , daß ich es mir ein bischen schwer mache, den Einstieg zu bekommen.

Habe neulich erst mit C bzw. C++ angefangen.

(ohne Vorkenntnisse)

Aber ich werde es einmal mit qsort probieren. Ich wollte eigentlich in meinem Beispiel die Werte sortieren die man als User eingibt.

Werd es mal probieren

Thx