Kurs:Algorithmen und Datenstrukturen/Kapitel 2/BubbleSort

Herleitung

Ausgehend von der Definition eines sortierten Arrays

$a_i\le a_{i+1},i=1\dots n-1$

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

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

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).

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 $a_i$ das groesste Element ist, $a_i\le a_{i+1}$ immer versagen wird und das Element an der Stelle $a_{i+1}$ vertauscht wird. Das gleiche spielt sich dann ab, bis das größte Element am Ende des Arrays bei $a_n$ sitzt. Aus dieser Position fällt es auch nie wieder heraus, denn, ist $a_n$ das größte Element, so wird $a_{n-1}\le a_n$ fuer jede Besetzung von $a_{n-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 Hinaufrutschens der Elemente, ähnlich des Aufsteigens von Blasen in einer Flüssigkeit, heißt dieser Algorithmus in der Literatur auch BubbleSort.

Was kostet das?

Worst-Case Analyse

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

Im k-ten Durchlauf werden $n-k$ Vergleiche benötigt.

Average-Case Analyse

Die average-case Analyse ist wesentlich komplizierter. Wir betrachten hierzu das Schicksal eines einzelnen Elements $a_k$. Um an der richtigen Stelle im Array zu landen, wird $a_k$ 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 $i$-te 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 $i$-te Stelle gehört und mit Wahrscheinlichkeit $\frac{1}{n}$ an der Stelle $k$ sitzt, ist somit

$\begin{array}{cc}V(i)& =\frac{1}{n}\sum _{k=1}^n[l(i,k)+r(i,k)]\\ & =\frac{1}{n}\sum _{k=1}^n[\frac{n-i}{n-1}(k-1)+\frac{i-1}{n-1}(n-k)]\\ & =\dots \\ & =\frac{n-1}{2}\end{array}$

Die durchschnittliche Anzahl Vertauschungen ist somit unabhängig von der eigentlichen Stelle des Elements. 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 $𝒪(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_{𝗆𝖺𝗑})$, dass in einer Permutation von $n$ Elementen kein Element weiter als $d_{𝗆𝖺𝗑}$ rechts von seiner angestammten Position steht.

Für $d_{𝗆𝖺𝗑}=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:

$P_r(n)=1$

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

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

Für $d_{𝗆𝖺𝗑}=n-2$ ist die Lage ähnlich: wir können $e_1$ weder an der Stelle $a_n$ noch $a_{n-1}$ platzieren und $e_2$ nicht an der Stelle $a_n$ hinlegen. Wir haben also für $e_1$ $(n-2)$ von $n$ und für $e_2$ nur $(n-2)$ von $(n-1)$ (wir haben ja schon $e_1$ 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

$\begin{array}{cc}{P}_r(n-k)& =\prod _{i=0}^{k-1}\left(\frac{n-k}{n-i}\right)\\ & =(n-k{)}^k\frac{(n-k)!}{n!}\\ \end{array}$

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

$\begin{array}{cc}{P}_r(n-k+1)-P_r(n-k)& =(n-k+1{)}^{k-1}\frac{(n-k+1)!}{n!}-(n-k{)}^k\frac{(n-k)!}{n!}\\ & =\frac{1}{n!}((n-k+1{)}^{k-1}(n-k+1)!-(n-k{)}^k(n-k)!)\\ & =\frac{(n-k)!}{n!}((n-k+1{)}^k-(n-k{)}^k)\end{array}$

• 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 Binomialverteilung...