Bubble sort


  • 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