Kurs:Algorithmen und Datenstrukturen/Kapitel 2/BubbleSort

Aus Wikiversity

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

[Bearbeiten] BubbleSort

[Bearbeiten] Herleitung

Ausgehend von der Definition eines sortierten Arrays

a_i \leq a_{i+1}, \quad i = 1 \dots n-1

(wir verwenden hier das "\leq" fuer eine allgemeine Ordnungsrelation), koennen wir einen ersten, naiven Algorithmus zum sortieren eines Arrays konstruieren:

Wir durchlaufen das Array und vergleichen dabei jedes Element ai (beginnend bei i = 0) mit dem darauffolgenden Element ai + 1. Sind die zwei Elemente nicht sortiert, so werden sie vertauscht. Wir wiederholen diesen Vorgang bis das Array sortiert ist.


[Bearbeiten] Implementierung in Oberon

In Oberon würde eine PROCEDURE, welche folgenden Algorithmus für Daten des Typs INTEGER implementiert, wie folgt aussehen:

 1. PROCEDURE BubbleSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
 2.     VAR
 3.         i : INTEGER;
 4.         temp, swaps : INTEGER;
 5.     BEGIN

            (* Arraylänge überprüfen *)
 6.         IF n > LEN(a) THEN
 7.             Out.String("Error: n groesser als Arraylaenge!"); Out.Ln;
 8.             RETURN;
 9.         END;

            (* Wiederhole bis alles sortiert ist... *)
10.         REPEAT
11.             swaps := 0;

                (* Für jedes Element... *)
12.             FOR i := 0 TO n-2 DO

                    (* Vergleiche und Vertausche mit Nachbar *)
13.                 IF ~(a[i] <= a[i+1]) THEN
14.                     temp := a[i]; a[i] := a[i+1]; a[i+1] := temp;
15.                     INC(swaps);
16.                 END

17.             END

18.         UNTIL swaps = 0;
19.     END BubbleSort;

Am Anfang unserer Prozedur (Zeile 6) überprüfen wir zuerst, ob n innerhalb der Grenzen des Arrays liegt. Die Schleife von Zeile 10 bis 18 ist die Hauptschleife unseren Algorithmus. Wir beachten, dass die Schleife in Zeile 12 von 0 bis n-2 geht, da die Array-Nummerierung in Oberon bei 0 anfängt.

Die Variable swaps gibt an, wieviele Vertauschungen im Durchgang vorgenommen wurden. Wurde nichts vertauscht, so ist unser Array gemäß Definition sortiert und wir können aufhören (Zeile 14).

[Bearbeiten] Funktioniert sowas überhaupt?

Wir können unsere Sortierprozedur in ein Modul namens Sorting packen und mit ein paar Zahlen testen:

MODULE Sorting;

    IMPORT
        In, Out;
        
    CONST
        MaxN = 100;
        
    PROCEDURE BubbleSort* ( VAR a : ARRAY OF INTEGER ; n : INTEGER );
        ...
        END BubbleSort;
        
    PROCEDURE Go*;
        VAR
            a : ARRAY MaxN OF INTEGER;
            i, n : INTEGER;
        BEGIN
            In.Open; In.Int(n);
            FOR i := 0 TO n-1 DO In.Int(a[i]); END;
            BubbleSort(a,n);
            FOR i := 0 TO n-1 DO Out.Int(a[i],10); END;
            Out.Ln;
        END Go;

BEGIN
    Out.Open;
END Sorting.

Sorting.Go 5 3 4 2 5 1 ~

Und sie funktioniert tatsächlich. Die übergebenen Zahlen werden in aufsteigender Reihenfolge sortiert und ausgegeben. Funktioniert das aber auch auf jeden Fall?

Was sicher ist, ist dass im ersten Durchlauf das (nach unserer Relation) größte Element zur letzten Stelle des Arrays verschoben wird. Dies kann man damit zeigen, dass, falls ai das groesste Element ist, a_i \leq a_{i+1} immer versagen wird und das Element an der Stelle ai + 1 vertauscht wird. Das gleiche spielt sich dann ab, bis das größte Element am Ende des Arrays bei an sitzt. Aus dieser Position fällt es auch nie wieder heraus, denn, ist an das größte Element, so wird a_{n-1} \leq a_n fuer jede Besetzung von an − 1 gelten.

Sitzt das größte Element nach dem ersten Durchlauf am Ende des Arrays, so kann das zweitgrößte Element nach dem gleichen Prinzip ungehindert zur zweitletzten Stelle rutschen, und so weiter bis alle Elemente sortiert sind.

Wegen dieses Hinaufrutshchen der Elemente, ähnlich Blasen in einer Flüssigkeit, heißt dieser Algorithmus in der Literatur auch BubbleSort.

[Bearbeiten] Was kostet das?

[Bearbeiten] Worst-Case Analyse

Im ersten Durchlauf führt BubbleSort n − 1 Vergleiche und, im schlimmsten Fall n − 1 Vertauschungen aus.

Im zweiten Durchlauf führt er, gemäss unserem Algorithmus, auch wieder n − 1 Vergleiche, jedoch maximal nur n − 2 Vertauschungen aus. Dies ruht daher, dass nach dem ersten Durchlauf, wie wir oben schon gesehen haben, das größte Element schon am Ende des Arrays steht und daher auch garantiert nicht mehr vertausch wird.

Im dritten Durchlauf führt der Algorithmus wieder n − 1 Vergleiche aus und, der Argumentation des letzten Durchlaufs folgend, nur noch n − 3 Vertauschungen aus. Nach den ersten beiden Durchläufen befinden sich die zwei größten Elemente schon in der richtigen Reihenfolge am ende des Arrays und müssen daher, auch im schlimmsten Fall, nicht vertauscht werden.

Allgemein können wir sagen, dass im iten Durchlauf in jedem Fall n − 1 Vergleiche und im schlimmsten Fall n − i Vertauschungen ausgeführt werden.

Wieviele Durchläufe sind aber nötig, bis das Array sortiert ist? Im schlimmsten Fall wird pro Durchlauf nur das jeweils größte unsortierte Element richtig platziert -- sprich: im ersten Durchlauf das größte Element, im zweiten das zweitgrößte, usw... Im n − 1sten Durchlauf platzieren wir spätestens noch das zweite Element und es steht dann noch das erste Element schon an der richtigen Stelle, weil es sonst nirgendswo sein kann. Wir brauchen also maximal n − 1 Durchläufe.

Im worst-case benötigt BubbleSort also n − 1 Durchläufe mit je n − 1 Vergleiche und n − i Vertauschungen. Zusammengesetzt ergibt das

\sum_{i=1}^{n-1} (n-i) \quad = \quad \frac{n^2-n}{2} \quad \in \quad \mathcal O(n^2)

[Bearbeiten] Average-Case Analyse

Die average-case Analyse ist wesentlich komplizierter. Wir betrachten hierzu das Schicksal eines einzelnen Elements ak. Um an der richtigen Stelle im Array zu landen, wird ak von allen Elementen, welche größer sind als es selber und links von ihm liegen, "überholt" werden. Zudem muss es selber alle Elemente, welche kleiner sind als es selber und rechts von ihm liegen, selber überholen.

Für ein Element an der Stelle k, welches eigentlich an die Stelle i gehören würde, ist die durchschnittliche Anzahl Elemente, welche größer wären, aber links von ihm liegen

l(i,k) = \frac{n-i}{n-1}(k-1)

Anders ausgedrückt: wählen wir (k − 1) Elemente aus, die mit einer Wahrscheinlichkeit \frac{n-i}{n-1} kleiner sind als das ite Element. Analog dazu sitzen im Durchschnitt rechts von unserem Element

r(i,k) = \frac{i-1}{n-1}(n-k)

Elemente, die kleiner wären als unser Element. Die zu erwartende Anzahl Vertauschungen für ein Element, welches an die ite Stelle gehört und mit Wahrscheinlichkeit \frac{1}{n} an der Stelle k sitzt, ist somit

V(i) = \frac{1}{n}\sum_{k=1}^n \left[ l(i,k) + r(i,k) \right]
= \frac{1}{n}\sum_{k=1}^n \left[ \frac{n-i}{n-1}(k-1) + \frac{i-1}{n-1}(n-k) \right]
= \frac{n-1}{2}

Die durchschnittliche Anzahl Vertauschungen ist somit unabhängig von der eigentlichen Stelle des Elemenentes. Bei n Elementen haben wir somit im Durchschnitt

\frac{1}{2}\frac{n(n-1)}{2} = \frac{n(n-1)}{4}

Vertauschungen. Der zusätzliche Faktor 1 / 2 kommt daher, dass jede Vertauschung beiden vertauschten Elementen zugute kommt. Die Anzahl Vertauschungen im average-case ist somit auch in der Größenordnung \mathcal O(n^2).

Um die Anzahl der durchschnittlich zu erwartenden Durchläufe zu berechnen, müssen wir beachten, dass pro Durchlauf eines der größeren Elemente links weggeschoben wird. Die kleineren Elemente rechts können in einem einzigen Durchlauf übersprungen werden. Dies geschieht aber selten in einem einzigen Zug: es können rechts größere Elemente dazwischenliegen, welche unser Element ausbremsen. Es bestimmt also dasjenige Element, welches die meisten Durchläufe benötigt, wieviele Durchläufe im Schnitt notwendig sind. Dieses Element ist dasjenige, für das k − i maximal ist -- also das Element, das am weitesten rechts von der ihm zugehörigen Stelle steht.

Wir betrachten die Wahrscheinlichkeit P_r(d_{\mathsf{max}}), dass in einer Permutation von n Elementen kein Element weiter als d_{\mathsf{max}} rechts von seiner angestammten Position steht.

Für d_{\mathsf{max}}=n ist die Lösung trivialerweise 1, denn es kann beim besten Willen kein Element n Schritte von seinem angestandenen Platz stehen, weil das Array gerade mal n Elemente hat:

Pr(n) = 1

Die Lösung für d_{\mathsf{max}}=n-1 ist ähnlich trivial: einen Abstand von n − 1 ist nur dann möglich, wenn das kleinste Element -- nennen wir es e1 an der letzten Stelle im Array an steht. Wir haben also nur (n − 1) von n Möglichkeiten, e1 irgendwo unterzubringen:

P_r(n-1) = \frac{n-1}{n}

Für d_{\mathsf{max}}=n-2 ist die Lage ähnlich: wir können e1 weder an der Stelle an noch an − 1 platzieren und e2 nicht an der Stelle an hinlegen. Wir haben also für e1 (n − 2) von n und für e2 nur (n − 2) von (n − 1) (wir haben ja schon e1 dazwischen platziert) Möglichkeiten:

P_r(n-2) = \left(\frac{n-2}{n}\right) \left(\frac{n-2}{n-1}\right)

Folgt man dieser Logik weiter, erhalten wir die Formel

Pr(n − k) = \prod_{i=0}^{k-1} \left(\frac{n-k}{n-i}\right)
= (n-k)^k \frac{(n-k)!}{n!}

Die Wahrscheinlichkeit nun, dass ein unsortiertes Array der Länge n einen maximalen rechten Abstand von genau d_{\mathsf{max}} = n-k enthält ist

Pr(n − k + 1) − Pr(n − k) = (n-k+1)^{k-1} \frac{(n-k+1)!}{n!} - (n-k)^k \frac{(n-k)!}{n!}
= \frac{1}{n!} \left( (n-k+1)^{k-1} (n-k+1)! - (n-k)^k (n-k)! \right)
= \frac{(n-k)!}{n!} \left( (n-k+1)^k - (n-k)^k \right)
  • Durchschnittstiefe = \sum_{k=0}^{n} (P_r(n-k+1) - P_r(n-k))(n-k)
  • gibts dafür eine elegante, geschlossene Form? Sieht aus wie eine Bionmialverteilung...
Von „http://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Kapitel_2/BubbleSort“
Persönliche Werkzeuge