Hallo liebe Delphi Forum Mitglieder,
ich bin ganz am Anfang meiner IT Karriere und benötige etwas Hilfe von euch. Ich bin seit kurzem in der Schule in einem Informatik Kurs und habe jetzt einige Fragen. Im Moment beschäftigen wir uns gerade mit verschiedenen Sortier-Algorithmen.

Ich habe bei Wikipedia folgenden Pseudo Code für Bubble Sort gefunden:

Mir ist klar, dass man es so nicht programmieren kann, aber ich will eigentlich auch nur die Idee, die dahinter steckt, verstehen. Ich versuche diese zu erklären, wenn ich Fehler mache, wäre ich froh, wenn mich jemand darauf hinweisen würde... los gehts.

Man hat eine Prozedur mit dem bubbleSort. A ist dabei die die Liste mit Elementen, die verwendet wird. n stellt die Länge dieser Liste A dar. Nun beginnt man theoretisch mit einer if-Prozedur, da diese immer wieder wiederholt werden soll (mit repeat) bis ein anderes Ereignis eintritt. Warum setzt man das "vertauscht" am Anfang auf false?
Man beginnt dann mit den Zahlen in der Liste. Diese beginnen bei 1 und enden bei n-1, das bedeutet beim vorletzten. (Warum?)
Wenn so eine Liste vorliegt beginnt man mit dem eigentlichen. Man vergleicht eine Zahl der Liste A[i] mit einer anderen. Was ich dabei jedoch nicht verstehe, warum denn [i+1]? Wenn ich annehme, dass i=1. Dann ist doch 1 automatisch kleiner als i+1 (1+1). Diesen ganzen Aspekt habe ich leider überhaupt nicht verstanden.
Wie auch immer, dann wird komischerweise vertauscht auf true gesetzt. Bei dem Rest blicke ich auch überhaupt nicht durch.
Wie dieser Sortier Algorithmus in Wirklichkeit funktioniert weiß ich, aber ich komme einfach nicht mit dem Code klar.

Ich würde mich wirklich freuen wenn mir das jemand erklären kann. Es ist nicht besonders schön, wenn man schon den Anfang dieser Sprache nicht versteht....
Danke,
Denkt

Moderiert von Narses: Code-Tags hinzugefügt
Moderiert von Narses: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Mi 26.05.2010 um 14:39

Hi,

Ich zitiere meinen Zusammenschrieb von Algorithmen und Datenstrukturen aus meinem 2. Semester.

Sortieren durch direktes Vertauschen (Bubble Sort)
Funktionsweise
Man geht von hinten her durch und betrachtet immer die Paare (n, n-1), (n-1, n-2), (n-2, n-3) und so weiter. Wenn das Element das hinten steht kleiner ist als das vordere wird es mit diesem vertauscht.
Beispiel mit dem Array [3,8,2,1,5]
Die äußere For-Schleife beginnt bei 1 und läuft bis 4.
Die innere beginnt bei 5 und betrachtet nun 5 und 1. Da 1 nicht größer als 5 ist wird nichts vertauscht. [3,8,2,1,5]
Dann betrachtet die Schleife 1 und 2. 1 ist kleiner als 2, also werden die 1 und die 2 vertauscht. [3,8,1,2,5]
Dann betrachtet man 1 und 8. Die 1 ist wieder kleiner also wird wieder vertauscht. [3,1,8,2,5]
Zuletzt betrachtet man die 3 und 1. Die 1 ist wieder kleiner und es wird wieder getauscht: [1,3,8,2,5].
Nun erhöht sich die for-Schleife um 1 und steht auf 2.
Die zweite For-Schleife läuft immer nur bis zu i, also wird ab jetzt das 1. Element nicht mehr betrachtet.
Der zweite Durchlauf:
[1,3,8,2,5]
[1,3,2,5,8]
[1,2,3,5,8]
Es finden insgesamt n-1 Durchläufe statt.


Stabilität
Auch Bubble-Sort ist genauso wie Sortieren durch abzählen und Sortieren durch direktes Auswählen (Selectionsort) stabil.
Das liegt daran, dass liegt wie beim Selectionsort daran, dass man man die Liste von vorne nach hinten durchgeht. Wenn man ein kleines Element nach immer weiter nachvorne schiebt, dann wird dieser Lauf unterbrochen sobald es auf ein gleichgroßes Element trifft, denn es wird nur vertauscht, wenn das vordere Element kleiner ist! Auch hier gilt wieder, würde man das echt-kleiner durch kleiner-gleich austauschen wäre das Verfahren nicht mehr stabil, da das Element das weiter hinten einem gleichgrossen Element vorgeschoben wird. Zwar wird dieses Element später selbst betrachtet, aber es kann passieren, dass es nicht mehr auf das andere trifft, da dieses bereits nach ganz vorne gerutscht ist und die erste For-Schleife verhindert, dass es dieses Element noch betrachtet wird.

Laufzeit
Wie bei den anderen Verfahren auch beträgt die Laufzeit O(n^2) für die Schlüsselvergleiche, da in der Vergleichsphase immer folgende Vergleiche notwendig sind:
(n-1) + (n-2) + ... 1 = n(n-1) / 2 = O(n^2).
Die mittlere Anzahl von Vertauschungen beträgt:
n*(n-1) / 4 = O(n^2).

Verbesserungen
Man könnte einbauen, dass ein Durchlauf der inneren for-Schlauf in dem nichts vertauscht wird direkt zum Abbruch führt. Denn wenn nichts vertauscht wird bedeutet das ja, dass kein kleiner ist als sein Vorgänger, was wiederrum bedeutet, dass das Array sortiert ist.
Man kann mit zwei gegeneinanderlaufenden For-Schleifen arbeiten: Einmal wird von hinten her durchgegangen und einmal von vorne her. Das hätte den Effekt, dass nicht nur die kleinen Schlüssel sehr schnell nach vorne wandern, sondern auch die großen Schlüssel. Das gepaart mit der Abbruchbedingung, dass abgebrochen wird wenn innerhalb eines Durchgangs keine Vertauschung stattgefunden hat.
Diese Verbesserungen sparen aber leider nur Schlüsselvergleiche und keine Vertauschungsoperationen, weswegen auch damit die Laufzeit O(n^2) bleibt!

Hey

Danke für deine Hilfe. Das hat mir schon teilweise geholfen, jedoch bei den genauen Fragen von mir, hilft es mir nicht weiter.

Denker

Wobei es ja auch unterschiedliche Varianten gibt wie das Zählen vom letzten oder vom ersten Wert.

Denkt hat folgendes geschrieben :

Es ist nicht besonders schön, wenn man schon den Anfang dieser Sprache nicht versteht....

Den Anfang der (Programmier-)Sprache oder den des (Sortier-)Algorithmus'?

Der Unterschied sollte klarsein oder schleunigst klarwerden.

Der Mensch ist - wie die meisten Tiere - ein Augentier. Zum Verständnis helfen deshalb visuelle Eindrucke oft mehr als viele Wörter, Sätze oder gar Zeilen (der älteste (Wahrnehmungs-)Sinn ist einfach der ausgereifteste und kann die meisten Informationen zum Gehirn transportieren, das wiederum zur Verarbeitung gerade dieser Informationen am ehesten bzw. meisten optimiert ist). Deshalb meine Anregung: Besorg' Dir mein Programm Sortierkino (auch in diesem Forum) und schaue, wie die einzelnen Sortieralgorithmen wirken. Von den Exoten, die intern Baumstrukturen verwenden (AVL- und B-Sort), und auch den speziellen Algorithmen einmal abgesehen, ist m.E. recht gut zu erkennen, wie die Algorithmen funktionieren.

Hey

Mit verstehen meine ich den Sortier Algorithmus. Das Sortierkino ist wirklich cool, habe jetzt etwas damit rumgespielt und von der Wirkung her verstehe ich den Algorithmus. Vielen Dank für dieses Programm. Jetzt muss ich nur noch den Code besser verstehen. Es genügt völlig der Pseudo Code, aber manches verstehe ich dennoch nicht.

Denkt

Bubblesort hat den Namen daher, weil die großen Elemente wie eine Blase im Wasser langsam nach oben steigen.

Oder anders: Man läuft mit "Vergleichsblasen" über die Zahlen. In einer solchen Vergleichsblase sind immer genau zwei benachbarte Zahlen drin. Wenn die Zahlen die Nummern 1 bis n haben, startet die Blase mit dem Paar (1,1) und endet mit dem Paar (n-1, n). Wenn der Starpunkt der Blase "i" ist, dann läuft die Blase also von 1 bis n-1. Das ist die innere Schleife und erklärt deren Grenzen.

Im Verlauf des Algorithmus wird nun an jeder Blasenposition von 1 bis n-1 überprüft, ob die beiden Element in dieser Blase richtig sortiert sind. Wenn ja, ist alles ok. Wenn nicht, dann ist die Folge noch nicht sortiert. Um etwas mehr Ordnung reinzubringen, vertauscht man diese beiden Elemente - das ist dann auf jeden Fall besser als vorher.

Bubblesort ist fertig, wennn man einmal von 1 bis n-1 komplett durchgebubblet ist, ohne auch nur ein Element zu vertauschen. Am Anfang eines Durchlaufs hat man noch nichts vertauscht (man startet ja eine neue Blase) - also setzt man vertauscht := False. Wenn man ohne vertauschen durchgekommen ist, ist die Folge sortiert. Ansonsten wurde vertauscht beim tauschen auf True gesetzt, und man muss eine neue Bubble starten - das macht die äußere Schleife.

Die Zeile n := n - 1 gegen Ende des Codes kann man auch weglassen. Die Idee dahinter ist die: Wenn die erste Blase ganz durchgebubblet ist, steht das größte Element auf jeden Fall ganz hinten. D.h. die nächste Blase muss gar nicht bis zum Ende laufen - denn da passiert ja sowieso nichts mehr. Nach der zweiten Runde ist dann das zweitgrößte Element an vorletzter Setlle usw.

@Gausi: Vielen, vielen Dank. Durch dich ist mir einiges klarer geworden.
Würde man anstatt von 1 bis n-1, von 1 bis n laufen, hätte man die 0 noch integriert oder?

Wirklich vielen Dank für die Antworten

Denkt

Nein, in der von dir geposteten Umsetzung, in der jeweils Item und Nachfolger verglichen werden, würde man auf die Indizes 1..n+1 zugreifen. So oder so würde es aber krachen .

Beachte aber: Wie in den meisten Sprachen beginnen Delphi-Arrays/Listen mit dem Index 0. Das letzte Item wäre damit n-1, die Schleife müsste von 0 bis n-2 laufen. Auch falls ihr euch gerade nur mit der Theorie befasst, kannst du das schon einmal im Hinterkopf behalten .

Hm, verstehe ich leider gerade überhaupt nicht mehr...
Meinst du, du kannst mir nochmal genauer das n-1 erklären?

Wenn das erste Item den Index 0 hat, welchen hat dann das letzte, also n-te?

n-1, oder?

Eben. Das war doch deine Frage, oder?

Danke.... ich habe es eben einfach nicht kapiert

Es gibt da noch die ganz "dumme" Umsetzung von BubbleSort:



Die ist einfacher zu verstehen (da kürzer).

Denkt hat folgendes geschrieben :

Dann ist doch 1 automatisch kleiner als i+1 (1+1). Diesen ganzen Aspekt habe ich leider überhaupt nicht verstanden.

Du darfst dabei i (=Index) nicht mit A[i] verwechseln.

Im Endeffekt kannst du dir das so vorstellen: Du hast einen Kartenstapel von 1-1000. Stell dir vor die liegen alle in einer langen Reihe rum (unsortiert). Jetzt ist es doof (aber nicht unbedingt langsamer), die Kleinste rauszusuchen, da musst du ja ne halbe Stunde suchen bis du die gefunden hast. Wenn du es nach Bubble Sort machst gehst du so vor:

Du gehst ganz an den Anfang der Reihe. Jetzt guckst du. Hat die Karte1 oder die Karte2 den höheren Wert? (1 und 2 sind in dem Fall der Index i. i hat nichts mit dem Wert zu tun, der auf der Karte steht = A[i]). Die Karte mit dem höheren Wert packst du nach rechts, die Karte mit dem niedrigeren Wert nach links.

Beispiel:
5 | 3 | ...
=>
3 | 5 | ...

ok, jetzt das selbe, aber mit dem nächsten Kartenpaar. Wir vergleichen jetzt Karte2 und Karte3, die kleinere kommt nach links, die größere nach rechts.

3 | 5 | 1 | ...
=>
3 | 1 | 5 | ...

Das machen wir jetzt solange, bis wir am Ende der Kartenreihe angekommen sind. Der letzte Vergleich ist jetzt Karte(N-1) mit KarteN. Da wir immer Karte i und i+1 vergleichen, sollten wir i nicht auf N setzen, denn dann wird ja im letzten Vergleich N mit N+1 verglichen...Karte(N+1) gibt es aber garnicht...das ist natürlich suboptimal und führt dann zu einem Fehler. (In unsrem Beispiel liegt zum Beispiel am Ende der Kartenreihe ein Apfel... KarteN mit Apfel vergleichen...dumm wie der Computer ist versucht er das, aber das geht dann irgendwo schief.)

Ok, jetzt sind wir einmal die Reihe durchgegangen und haben die Nachbarn jeweils miteinander verglichen (und vertauscht wenn nötig). Der Witz ist jetzt, dass nun, nach einem Durchlauf, die GRÖSSTE Karte am Ende liegt. Muss man sich vielleicht kurz überlegen. Da die größere der beiden verglichenen Karten jedesmal an die rechte Stelle kommt, ist dann am Ende die allergrößte Karte ganz rechts. Prima. Jetzt machen wir das einfach für die Restliste mit der Länge n-1 wieder. Dann ist ja die Größte der Restliste (also die Zweit-Größte der gesamten Liste) auch wieder nach rechts gewandert. Das machen wir jetzt solange, bis wir (n-1) mal die größte Zahl nach rechts geschoben haben. Fertig ist die Sortierung.

Wenn du das nicht gleich verstehst, dann mach einfach mal das Stur nach Schema aufm Papier. Eigentlich alles, was man zu Bubble-Sort wissen muss, ist, dass er jeweils 2 Nachbarn(!) vergleicht und passend vertauscht. Das ist das Herzstück.

Xion hat folgendes geschrieben :

Es gibt da noch die ganz "dumme" Umsetzung von BubbleSort:

Pfft, das kann ich überbieten .


Denn der Worst Case - ein Element, das von ganz rechts nach ganz links wandert - benötigt (so oder so) n-1 Durchgänge.

Hallo

Vielen Dank für die ganzen Antworten, jetzt habe ich es wirklich verstanden.
Meine nächste Frage kommt jedoch bestimmt

Denkt