Bubble sort



  • 5,6, 3,1,2

    Aber zum 2.PseudoCode nochmal . Hier wird doch swapped auf false gelassen weil A[i] kleiner A[i+1] ist. Dann bricht die Schleife ab. Aber das Array ist immer noch unsortiert. Ist der 2.Pseudo Code falsch ????

    Sorry die For- Schleife wird ja unabhängig davon trotzdem zu Ende gelaufen 🙂



  • blurry333 schrieb:

    Ist der bubble Sort bei sortierten Daten der beste Sortieralgorithmus der WElt ??

    Eine Erkennung ob die Daten bereits sortiert sind, kannst du vor jeden Sortieralgorithmus stricken. Bubblesort ist aber IMHO der primitivste Sortieralgorithmus der Welt.



  • Z schrieb:

    Eine Erkennung ob die Daten bereits sortiert sind, kannst du vor jeden Sortieralgorithmus stricken.

    Bist du dir da sicher ? Ich glaub eher das geht bei den anderen nicht. Nehmen wir mal den einfach Selection Sort . Wie willst du es da machen . Oder beim Quicksort etc.



  • Stimmt, es ist unmöglich, herauszufinden, ob eine Sequenz sortiert ist. 🙄



  • blurry333 schrieb:

    Z schrieb:

    Eine Erkennung ob die Daten bereits sortiert sind, kannst du vor jeden Sortieralgorithmus stricken.

    Bist du dir da sicher ? Ich glaub eher das geht bei den anderen nicht. Nehmen wir mal den einfach Selection Sort . Wie willst du es da machen . Oder beim Quicksort etc.

    Wir gehen zum Beispiel alle Elemente von Index 0 bis n-1 durch und testen ob das Folgeelement >= dem aktuellen Element ist. Trifft das auf alle zu, dann ist die Folge sortiert.



  • Ja klar. ABer das entspricht ja nicht mehr dem Selection Sort. Das ist ja wieder der Bubble Sort wo immer die benachbarten verglichen werden. Übrigends ist der Insertion Sort auch optimal bei einer sortierten Folge. Der ist sogar noch besser als der Bubble Sort !!



  • blurry333 schrieb:

    Ja klar. ABer das entspricht ja nicht mehr dem Selection Sort. Das ist ja wieder der Bubble Sort wo immer die benachbarten verglichen werden. Übrigends ist der Insertion Sort auch optimal bei einer sortierten Folge. Der ist sogar noch besser als der Bubble Sort !!

    Es gibt wohl nichts Simpleres und laufzeitmäßig Günstigeres als einmal alle benachbarten Elemente eines Arrays zu vergleichen, um festzustellen ob es sortiert ist oder nicht. Kannst mich aber gern davon überzeugen dass ich falsch liege.


  • Mod

    Das ich in diesem Thread antworte 🙄 .

    Aber Z hat einen Kommentar verdient:

    Z schrieb:

    Es gibt wohl nichts Simpleres und laufzeitmäßig Günstigeres als einmal alle benachbarten Elemente eines Arrays zu vergleichen, um festzustellen ob es sortiert ist oder nicht. Kannst mich aber gern davon überzeugen dass ich falsch liege.

    Das machen wir aber trotzdem nicht. Wir optimieren doch nicht auf den absoluten Ausnahmefall hin. Das ist eher etwas für den Anwendungscode, dass dieser uns keine Listen vorsetzt, von denen er wissen kann, dass sie schon sortiert sind (z.B. weil er sie uns vorher schon einmal vorgesetzt hat).

    Ansonsten gibt es auch noch haufenweise O(n*log(n))-Algorithmen, die einen best case O(n) haben. Ein paar davon haben sogar hinreichend kleine Konstanten, dass man sie in echten Programmen in Betracht ziehen kann, z.B. Timsort, der sogar speziell darauf ausgelegt ist, mit teilsortierten Listen gut umzugehen (der ist mWn sogar O(n), wenn die Daten genau rückwärts sortiert sind - der absolute Albtraum von Bubblesort).



  • SeppJ schrieb:

    Z schrieb:

    Es gibt wohl nichts Simpleres und laufzeitmäßig Günstigeres als einmal alle benachbarten Elemente eines Arrays zu vergleichen, um festzustellen ob es sortiert ist oder nicht. Kannst mich aber gern davon überzeugen dass ich falsch liege.

    Das machen wir aber trotzdem nicht. Wir optimieren doch nicht auf den absoluten Ausnahmefall hin.

    Wer ist wir? Wenn man fragt, ob Bubble Sort für einen absoluten Ausnahmefall der beste Algorithmus ist, dann muss eine Antwort, die einen auf den absoluten Ausnahmefall optimierten Algorithmus liefert, erlaubt sein.



  • SeppJ schrieb:

    Timsort

    Danke, kannte ich noch nicht. 👍


  • Mod

    Bashar schrieb:

    Wer ist wir?

    Der durchschnittliche Nicht-blurry333.

    hustbaer schrieb:

    SeppJ schrieb:

    Timsort

    Danke, kannte ich noch nicht. 👍

    Ich auch nicht, bis ich für meine Antwort auf Zs Beitrag mal auf Wikipedia nach Alternativen geguckt habe, die einen O(N) best case haben und sonst auch nicht schlecht sind. Scheint neu zu sein. Da sag mal einer noch, Sortieralgorithmen wären ein ausgelutschtes Thema 😃 .



  • SeppJ schrieb:

    Bashar schrieb:

    Wer ist wir?

    Der durchschnittliche Nicht-blurry333.

    Jetzt kann ich mir aussuchen, ob ich überaußerdurschnittlich oder ein blurry bin, na danke 🙂


  • Mod

    Bashar schrieb:

    Jetzt kann ich mir aussuchen, ob ich überaußerdurschnittlich oder ein blurry bin, na danke 🙂

    Heißt das, du würdest tatsächlich Sortierfunktionen schreiben, die zuerst einmal prüfen, ob es schon sortiert ist, obwohl dies kein Teil des eigentlichen Algorithmus ist?



  • Kommt drauf an. Normalerweise nicht, aber wir befinden uns seit blurry's Frage "Ist der bubble Sort bei sortierten Daten der beste Sortieralgorithmus der WElt ??" in einer hypothetischen Welt, in der es auf optimales Best-Case-Verhalten ankommt, und da bleibt dir wohl kaum etwas anderes übrig.



  • SeppJ schrieb:

    Heißt das, du würdest tatsächlich Sortierfunktionen schreiben, die zuerst einmal prüfen, ob es schon sortiert ist, obwohl dies kein Teil des eigentlichen Algorithmus ist?

    Wo ist das relevant ... ich kann mir vorstellen, dass IP-Pakete beim TCP-Protokoll meist in Reihenfolge ankommen. Wenn ich also einen Block Pakete habe wuerde ich in diesem Fall erst testen und dann sortieren. Das muss nicht mit allem im Buffer geschehen sondern kann blockweise geschehen, also immer fuer 5 zeitlich aufeinaderfolgende pruefen. Aber ich kenne mich mit dem Internet nicht so aus, vielleicht ist die Realitaet ganz anders.



  • Z schrieb:

    Ansonsten gibt es auch noch haufenweise O(n*log(n))-Algorithmen, die einen best case O(n) haben. Ein paar davon haben sogar hinreichend kleine Konstanten, dass man sie in echten Programmen in Betracht ziehen kann, z.B. Timsort

    MIt Konstante meinst du doch folgendes:

    In der Komplexitätsklasse n* log n wäre es z.B. : 20 * n * log n ;
    In der Komplexitätsklasse n wäre es z.B. : 10 * n ;

    Bei großen Datenmengen spielen die Konstanten doch kaum eine Rolle. Aber wenn ein linearer Algo eine große Konstante hat kann er bei wenigen Daten trotzdem langsamer als ein n² Algo sein oder ?



  • blurry333 schrieb:

    Z schrieb:

    Ansonsten gibt es auch noch haufenweise O(n*log(n))-Algorithmen, die einen best case O(n) haben. Ein paar davon haben sogar hinreichend kleine Konstanten, dass man sie in echten Programmen in Betracht ziehen kann, z.B. Timsort

    MIt Konstante meinst du doch folgendes:

    In der Komplexitätsklasse n* log n wäre es z.B. : 20 * n * log n ;
    In der Komplexitätsklasse n wäre es z.B. : 10 * n ;

    Bei großen Datenmengen spielen die Konstanten doch kaum eine Rolle. Aber wenn ein linearer Algo eine große Konstante hat kann er bei wenigen Daten trotzdem langsamer als ein n² Algo sein oder ?

    ja, damit meint er das


  • Mod

    hustbaer schrieb:

    ja, damit meint er das

    Nein, meine ich nicht. Aber ich mag blurry333 keine Komplexitätsklassen (oder irgendwas) erklären.



  • Öhm.
    Dann erklär es mir 🙂

    Ich meine, die Laufzeit von nem Sortieralgorithmus sollte man recht gut mit a + b*n + c*n*log(n) annähern können. Wobei a , b und c dann die Konstanten wären.

    Und wenn du nicht das meinst, dann würde mich schon interessieren was du mit Konstanten meinst.


Anmelden zum Antworten