Jabber Geschrieben 25. Mai 2002 Geschrieben 25. Mai 2002 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 ! Zitieren
Orffi Geschrieben 25. Mai 2002 Geschrieben 25. Mai 2002 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 Zitieren
nic_power Geschrieben 25. Mai 2002 Geschrieben 25. Mai 2002 Das einfachste duerfte sein, die entsprechende qsort() Routine aus der C-Bibliothek mit einzubinden ("man qsort"). Nic Zitieren
yamato Geschrieben 27. Mai 2002 Geschrieben 27. Mai 2002 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) Zitieren
Orffi Geschrieben 27. Mai 2002 Geschrieben 27. Mai 2002 "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 Zitieren
yamato Geschrieben 27. Mai 2002 Geschrieben 27. Mai 2002 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. Zitieren
Crush Geschrieben 27. Mai 2002 Geschrieben 27. Mai 2002 Mir persönlich scheint der Radix-Sort am schnellsten zu sein, sofern die Datenmenge und der Sortierbereich entsprechend begrenzt ist. Zitieren
nic_power Geschrieben 27. Mai 2002 Geschrieben 27. Mai 2002 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 Zitieren
Jabber Geschrieben 30. Mai 2002 Autor Geschrieben 30. Mai 2002 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 Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.