Zum Inhalt springen

Bubble vs. Quick - Sort


Jabber

Empfohlene Beiträge

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 !

Link zu diesem Kommentar
Auf anderen Seiten teilen

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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)

Link zu diesem Kommentar
Auf anderen Seiten teilen

"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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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. :)

Link zu diesem Kommentar
Auf anderen Seiten teilen

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

:P Werd es mal probieren

Thx

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...