Bubble sort



  • Laut wikipedia ist bubble sort bei einer schon gut sortierten Liste der beste Algorithmus da er die Sortierung erkennt. Aber bei diesem Pseudocode im selben Artikel , ist das meiner Meinung nach nicht der Fall oder ?

    bubbleSort(Array A)
      for (n=A.size; n>1; n=n-1){
        for (i=0; i<n-1; i=i+1){
          if (A[i] > A[i+1]){
            A.swap(i, i+1)
          } // ende if
        } // ende innere for-Schleife
      } // ende äußere for-Schleife
    


  • Beim Bubble sort wandert doch einfach das größte Element nach oben. Der Bubble sort erkennt doch deswegen nicht ob das array schon sortiert ist. Aber oft liest man das ??



  • Warum liesst du nicht einfach weiter. Bei so dummen Fragen frage ich mich, ob du nicht tatsaechlich ein Troll bist. Dementsprechend werden Antworten auf deine Fragen sich zukuenftig aendern.

    Allerdings nutzt diese einfachste Variante nicht die Eigenschaft aus, dass nach einer Iteration, in der keine Vertauschungen stattfanden auch in den restlichen Iterationen keine Vertauschungen mehr stattfinden. Der folgende Pseudocode berücksichtigt dies:



  • dann eben diesen hier 🙂

    bubbleSort2(Array A)
      n = A.size
      do{
        swapped = false
        for (i=0; i<n-1; ++i){
          if (A[i] > A[i+1]){
            A.swap(i, i+1)
            swapped = true
          } // ende if
        } // ende for
        n = n-1
      } while (swapped == true)
    


  • Dieses swapped = true macht den Bubble Sort im NOrmalfall ja noch langsamer da nach jeder Vertauschung swapped neu gesetzt wird. Aber bei sortierten DAten ist der bubble Sort schneller als Quicksort etc.



  • Und jetzt deine Frage bitte!



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



  • blurry333 schrieb:

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

    Nein, Bogosort ist der schnellste wenn die Daten bereits sortiert sind.



  • 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 🙂


Log in to reply