Prinzip-Erläuterung von BubbleSort

  • Hallo!


    An sich verstehe ich schon, wie BubbleSort funktioniert.
    Jedoch tue ich mich schwer bei der genauen Erläuterung des Struktogrammes.


    Habe hier mal ein Struktogramm und Beispiel für BubbleSort:


    [Blockierte Grafik: http://www.sky-divezone.de/Other/Sort.jpg]


    Also die äußere Schleife durchsucht ja das gesamte Array von hinten nach vorne durch und die innere Schleife ist für die Tauschvorgänge verantwortlich, richtig?


    Nur begreife ich nicht wirklich diese Schreibweisen wie "von (1) bis (n-1) ?(
    Was soll das darstellen? Dieses " (n-1) " bedeutet ja sicherlich, dass das Programm von hinten anfängt (also 5) und sich dann immer um eine Stelle weiter nach vorne bewegt und dort die beiden Zahlen miteinander vertauscht, oder? Aber was bedeutet diese " (1) "?


    Noch schlimmer wirds ja bei der zweiten Schleife :(
    Wieso ist "i=(n-1)"? Und wie muss ich die Vorgehensweise "von (-1) bis j" verstehen?


    Am Hilfreichesten wäre es, wenn mir jemand die Schrittfolge von Anfang bis Ende genau erklären könnte mit besonderem Bezug auf die verwendeten Variablen.


    Vielleicht ist es einfacher als gedacht, aber mit logischem Verstehen tue ich mich ab und zu etwas schwer ;)


    Danke für jede Hilfe!


    Rayne

  • (n-1) entspricht der 4


    Die erste schleife zählt von 1 bis 4 und die zweite zählt rückwärts von 4 nach 1 (bei dem Beispiel)


    Die Schleifen beschreibungen im Striktogramm kommen mir aber schlecht formuliert vor. Wenn man den Text liest denke zumindest ich nicht, dass es sich um eine Schleife handelt. Aber da bist du wohl schon selbst drüber gestolpert.


    Wo hast du die her?


    Richtiger wäre wohl


    Für j=1 in +1-Schritten bis zum Wert (n-1)


    Oder ganz eindeutig


    Für j von 1 bis (n-1) in +1-Schritten

  • Rayne schrieb:

    Zitat

    Also die äußere Schleife durchsucht ja das gesamte Array von hinten nach vorne durch und die innere Schleife ist für die Tauschvorgänge verantwortlich, richtig?

    so ist das nicht ganz richtig.


    Die innere Schleife durchsucht das Feld von hinten nach vorne und tauscht 2 benachbarte Zahlen, wenn die hintere kleiner ist als die größere. (z.B. bei j=1, i=2 werden 1 und 5 getauscht)


    Die äußere Schleife sorgt dafür, das dieser Vorgang exakt n-1, also in diesem Fall 4 mal wiederholt wird, da bei jedem Durchlauf der inneren Schleife im ungünstigsten Fall immer nur eine Zahl auf die richtige Postion gebracht wird (nämlich die kleinste Zahl, die noch in der neuen Suchmenge verbleibt).


    Sprich:
    (j=1) Beim ersten Durchlauf der inneren Schleife steht die 1 an der richtigen Stelle (nämlich a0).
    (j=2) Da diese jetzt richtig ist, muss beim zweiten Durchlauf der inneren Schleife diese nur noch bis zur zweitkleinsten Zahl suchen , also bis a1 usw.


    Das mal nur als Anmerkung. Zum Struktogramm hat ja Cepheiden schon was geschrieben.
    Hier möchte ich noch sagen, dass es sogar besser ist, die Indicies nicht bei 1 anfangen zu lassen sondern bei 0, da die Felder auch mit a0 beginnen. Das macht das Verstehen meiner Meinung nach etwas einfacher, weil damit automatisch die Variablen i und j den Felderindices entsprechen.
    (wobei dann z.B. bei j der höchste Index n-2 ist oder die Bedingung <N-1 sein muss :rolleyes: )

  • So, ich gibt wieder ein paar Unklarheiten ;)


    Diesmal gehts aber nicht nur um BubbleSort, sondern um den Vergleich von einfachen und komplexen Sortierverfahren.
    Ich dachte, ich eröffne nicht extra einen neuen thread dafür und schreibe meine Frage hier rein.


    Man sieht ja anhand vieler Zeitmessungen im Netz, dass Verfahren wie QuickSort, Mergesort und SelectionSort schneller arbeiten, als beispielsweise BubbleSort.


    Aber wie erkläre ich jetzt genau, dass die komplexen Sortierverfahren schneller arbeiten, als das einfache?


    Habe mir zwar die Funktionsweisen der genannten Algorithmen angesehen, aber richtige Begründungen für etwaige Zeitunterschiede habe ich nicht gefunden.


    Es gibt zwar diese Angaben für die Zeitkomplexität (n² bzw. n*log n), aber das als Begründung dürfte nicht ausreichen.


    Vielleicht kennt ihr die Begründungen?


    Wäre nett.


    Rayne

  • Zitat

    Es gibt zwar diese Angaben für die Zeitkomplexität (n² bzw. n*log n), aber das als Begründung dürfte nicht ausreichen.

    Doch, denn ehrlich gesagt, ist das sogar die (vermutlich) einzige Aussage, die man beweisen kann.
    Die Zeitkomplexität kann man meistens mathematisch nachweisen oder aber abschätzen. Sie ist damit sehr zuverlässig.
    Sie gibt ja an, wieviel Operationen durchgeführt werden müssen.


    Die Frage ist aber eher, was ist ein komplexer Algorithmus und was ein einfacher? So kann man Bubbelsort auch mit Abbruchsbedingungen erweitern, die den Algorithmus noch etwas schneller werden lassen (wenn die Menge nicht gerade komplett entgegen sortiert ist) und damit auch etwas komplexer.


    Die Begründung das andere Verfahren schneller arbeiten ist fast immer folgende: Zum einen mathematische Gründe, da es halt verschieden Möglichkeiten gibt Mengen zu sortieren und einige davon schneller sind als andere. Zum anderen untersuchen einige Algorithmen die durchsuchende Menge auf Besonderheiten und gehen dann während des Suchens darauf ein. Brechen als zB. rechtzeitig ab, wenn die Menge schon vorher fertig sortiert ist.


    Und wenn du dir die Zeitkomplexität von verschiedenen Algorithmen angeschaut hast, wirst du festgestellt haben, dass es immer einen besten Fall, einen mittleren Fall und einen schlechtesten Fall (worst case) gibt und die Verfahren da unterschiedlich abschneiden.

  • Zitat

    Original von Interstar
    [QUOTE]Und wenn du dir die Zeitkomplexität von verschiedenen Algorithmen angeschaut hast, wirst du festgestellt haben, dass es immer einen besten Fall, einen mittleren Fall und einen schlechtesten Fall (worst case) gibt und die Verfahren da unterschiedlich abschneiden.


    Genau deswegen ist auch Quicksort bei einer komplett engegengesetzt Sortierten Liste nicht schneller als Bubblesort

  • Noch eine Ergänzung:
    Wie ich schon schrieb, gibt die Zeitkomplexität ja an, wieviel Operationen durchgeführt werden müssen.
    Da aber jeder (Mikro)Prozessortyp eine andere Laufzeit für verschiedene Operationen hat, kann ein Algorithmus trotz mehr ausgeführter Operationen schneller sein als ein anderer, der weniger Operationen braucht. Nämlich dann, wenn genau diese sehr lange brauchen.


    Wenn man z.B. einen Mikroprozessor hat, der schlecht mit Arrays umgehen kann oder ein System wo Speicherplatz sehr knapp ist, dann bringt auch ein Algorithmus nix, der gerade viel Arrays benutzt oder Speicherplatzintensiv ist.

  • Danke, das hört sich doch schonmal gut an :)


    Jetzt würde mich noch interessieren, wie denn so eine Abbruchbedingung für BubbleSort aussehen könnte.


    Ich habe da mal was ausprobiert, bin mir aber nicht sicher, ob das so geht.


    Das Ding soll bedeuten, dass, wenn in der inneren Schleife keine Vertauschungen mehr stattgefunden haben, das Programm stoppt, anstatt ewig weiterzulaufen.


    [Blockierte Grafik: http://www.sky-divezone.de/Other/bubble.gif]


    Rayne

  • Nein so wie du dir das gedacht hast funktioniert das nicht, da würde die sortierung stoppen so wie das erstemal nicht getauscht werden müsste. Wenn du versuchst zu ermitteln ob die Liste sortiert ist musst du sie mindestens einmal mit dem 1. Elemnt vergleiche. Die abbruch bedingung kann alsoi nicht in der 2. Schleifen stehen

  • Hm, habe mir schon fast gedacht, dass das nicht alleine in der zweiten Schleife stehen darf...


    Aber so richtig komme ich nicht drauf, wie ich das nun korrekt umsetzen kann ?(


    Kannst du mir das mal vielleicht in Paint schnell scribbeln? ;)
    Wäre wirklich hilfreich!


    Rayne

  • Vielen Dank für das Struktogramm :)
    Sieht einleuchtend aus ;)


    Jetzt brauche ich dieses Struktogramm als PAP.
    Habe auch mal eins vorbereitet, bin mir jedoch bei der Abbruchbedingung nicht sicher, wo ich die einfügen muss (deshalb ist die Verbindung rot dargestellt):


    [Blockierte Grafik: http://www.sky-divezone.de/Other/PAP.jpg]


    Stimmt das so weit? Oder muss das verändert werden?


    Danke!


    Rayne

  • Nein so kann das nicht richtig sein.


    1. fehlt die Bedingung (du hast es ja an eine Auswahl angefügt)
    2. würde er wenn er einmal getauscht hat stehenbleiben denn nach Sortiert = false ist der Zweig ja am Ende


    Die schleifen an sich sind auch nicht vollständig.


    Schau dir mal das Beispiel in der Wikipedia an da ist eigentlich schon ganz gut erklärt

  • wie gesagt nicht alles im Netz und in Büchern ist richtig.


    Die rautenförmigen Objekte im PAP beschreiben nur Verzweigungen, mit ihnen allein kann man keine Zählschleife basteln, denn es muss ersichtlich werden wie und wo der Zählerwert erhöht wird.


    Am untersten Block fehlt keine Verzweigung sondern ein pfad zur Abfrage ob das Feld bereits sortiert ist (übrigens in der 1. Schleife nciht außerhalb). Dorthin führt übrigens auch der "Nein-Wert" der "ai+1 > ai" Abfrage.


    Nunja, sind halt einige Fehler drin. Ich hab auch das Gefühl du hast dir das Beispiel in der Wikipedia nicht angeschaut. Das ist zwar noch ohne Beschreibung aber ich denke du kannst die Zählschleife mit einer Einseitigen Auswahl/Verzweigung nachvollziehen.

  • Ja genau das begreife ich nicht, wie das richtig geschrieben wird.
    Es wird wohl kaum reichen, "+1" in die Raute dazuzuschreiben ?(


    Muss ich das aufsplitten und von mir aus 2 Anweisungen draus machen? Also in der ersten irgendwas wie "j=1" und in der zweiten "j=j+1"?
    Aber irgendwie geht das so ja auch nicht, denn so würde j ja nach jedem Durchlauf wieder auf 1 gesetzt werden :(


    Grr, verstehs nicht ;(