Kurs:Algorithmen und Datenstrukturen/Kapitel 2/BubbleSort

Aus Wikiversity
Zur Navigation springen Zur Suche springen

BubbleSort[Bearbeiten]

Herleitung[Bearbeiten]

Ausgehend von der Definition eines sortierten Arrays

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

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


Implementierung in Oberon[Bearbeiten]

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?[Bearbeiten]

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 das groesste Element ist, immer versagen wird und das Element an der Stelle vertauscht wird. Das gleiche spielt sich dann ab, bis das größte Element am Ende des Arrays bei sitzt. Aus dieser Position fällt es auch nie wieder heraus, denn, ist das größte Element, so wird fuer jede Besetzung von 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?[Bearbeiten]

Worst-Case Analyse[Bearbeiten]

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

Im k-ten Durchlauf werden Vergleiche benötigt.

Average-Case Analyse[Bearbeiten]

Die average-case Analyse ist wesentlich komplizierter. Wir betrachten hierzu das Schicksal eines einzelnen Elements . Um an der richtigen Stelle im Array zu landen, wird 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 , welches eigentlich an die Stelle gehören würde, ist die durchschnittliche Anzahl Elemente, welche größer wären, aber links von ihm liegen

Anders ausgedrückt: wählen wir Elemente aus, die mit einer Wahrscheinlichkeit kleiner sind als das -te Element. Analog dazu sitzen im Durchschnitt rechts von unserem Element

Elemente, die kleiner wären als unser Element. Die zu erwartende Anzahl Vertauschungen für ein Element, welches an die -te Stelle gehört und mit Wahrscheinlichkeit an der Stelle sitzt, ist somit

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

Vertauschungen. Der zusätzliche Faktor kommt daher, dass jede Vertauschung beiden vertauschten Elementen zugute kommt. Die Anzahl Vertauschungen im average-case ist somit auch in der Größenordnung .

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 maximal ist -- also das Element, das am weitesten rechts von der ihm zugehörigen Stelle steht.

Wir betrachten die Wahrscheinlichkeit , dass in einer Permutation von Elementen kein Element weiter als rechts von seiner angestammten Position steht.

Für ist die Lösung trivialerweise , denn es kann beim besten Willen kein Element Schritte von seinem angestandenen Platz stehen, weil das Array gerade mal Elemente hat:

Die Lösung für ist ähnlich trivial: einen Abstand von ist nur dann möglich, wenn das kleinste Element -- nennen wir es an der letzten Stelle im Array steht. Wir haben also nur von Möglichkeiten, irgendwo unterzubringen:

Für ist die Lage ähnlich: wir können weder an der Stelle noch platzieren und nicht an der Stelle hinlegen. Wir haben also für von und für nur von (wir haben ja schon dazwischen platziert) Möglichkeiten:

Folgt man dieser Logik weiter, erhalten wir die Formel

Die Wahrscheinlichkeit nun, dass ein unsortiertes Array der Länge einen maximalen rechten Abstand von genau enthält ist

  • Durchschnittstiefe =
  • gibts dafür eine elegante, geschlossene Form? Sieht aus wie eine Binomialverteilung...