28.5.1 Lösungen
 
Aufgabe 1 Für jeden Durchgang des Baumes benötigt man im worst case log2 (n-N) (N<n) Vergleiche. Andererseits wird der Baum n-Mal 'durchlaufen' , wobei genau ein Element seinen endgültigen Platz erhält. Somit ist der Gesamtaufwand:

A(n) = n * log2 (n-x) und damit
A(n)
Î O(n)*O(log n) und damit

= O (n*log n)

 
Aufgabe 2

Download:
Sortieren. java

public static void bubbleBiSort(String[] liste) {

  for (int li = 0, re = liste.length-1; li <= re; li++,re--) {

    for (int j = li + 1; j < re; j++) {

      if (liste[j].compareTo(liste[li])<0) {

        tausche(liste, li, j);

      }

      if(liste[j].compareTo(liste[re])>0){

        tausche(liste, re, j);

      }

      //erneute Vergleich nötig

      if (liste[j].compareTo(liste[li])<0){

          tausche(liste, li,j);

      }

      if (liste[j].compareTo(liste[li])<0) {

        tausche(liste, li, j);

      }

    }

  }

}
  Der Schleifenkopf der äußeren Schleife ist in zweifache Hinsicht interessant. Im Initialisierungsteil stehen zwei Deklarationen durch Kommata getrennt, ebenso im Dekrementierungs- bzw. Inkrementierungsteil.

for
(int li = 0, re = liste.length-1; li <= re; li++,re--

Der 'Marker' li steht zunächst auf dem ersten Element der Liste. re wird mit Hilfe der Feldlänge initialisiert, steht also zu Beginn auf der letzen Eintragung. Ein weiterer 'Marker', nämlich j, wandert von links (rechts von li bis re. Bei jedem Schritt wird der Wert an dieser Stelle zunächst mit li dann mit re verglichen. Ist der Wert bei j kleiner als bei li so werden die Inhalte vertauscht, ist der Wert bei j größer als der Wert re, wird auch vertauscht. Ist beides nicht der Fall, wandert j einfach weiter.  War aber ein Tausch notwendig, muss nach dem Vertauschen n och mal mit den Grenzen verglichen werden. Der Vorgang ist an Hand eines Schreibtischtestes veranschaulicht.
 

 
23 45 3 43 102 303 122 87 45 2 (1)
23 2 3 43 102 303 122 87 45 45 (2)
2 23 3 43 102 303 122 87 45 45 (3)
2 23 3 43 45 303 122 87 45 102 (4)
2 23 3 43 45 102 122 84 45 303 (5)
2 23 3 43 45 102 122 84 45 303 (6)
2 3 23 43 45 102 122 84 45 303 (7)
2 3 23 43 45 102 122 84 45 303 (8)
2 3 23 43 45 45 122 84 102 303 (9)
2 3 23 43 45 45 102 84 122 303 (10)
2 3 23 43 45 45 102 84 122 303 (11)
2 3 23 43 45 45 84 102 122 303 (12)
2 3 23 43 45 45 84 102 122 303 (13)
2 3 23 43 45 45 84 102 122 303 (14)
2 3 23 43 45 45 84 102 122 303 (15)
 
Der aktuelle Stelle
li ist gelb unterlegt, die aktuelle Stelle re rot. Der Marker j ist eine Stelle rechts von li gesetzt. Der Wert dort (45) ist größer als der Wert bei li (23), die Werte werden also nicht vertauscht. Dagegen muss 45 und 2 seinen Platz tauschen (1) -> (2). Das Beispiel zeigt, dass ein erneuter  Vergleich mit li gefolgt von einer Vertauschen nötig wird ((2) -> (3). Ohne weiteres Vertauschen wandert j (hell) bis j (dunkel) auf der Zahl 102 steht und mit re getauscht wird. Der erneute Vergleich mit li hat kein Tauschen zu Folge. Dies setzt sich fort, bis j links von li steht, die innere Schleife ist zu Ende. An dieser Stelle ist garantiert dass li und re auf das kleinste bzw. größte Element der Liste zeigen, diese Plätze sind also fertig sortiert. Für den nächsten Durchgang der äußeren Schleifewerden li inkremenrtiert und re dekrementiert, in der Tabelle erkennt man dies daran dass die gelb und rot markierten Plätze aufeinander zulaufen (5) -> (6). Für j beginnt das Spiel non Neuem. allerdings für die um 2 Plätze kleineren Liste. Das Verfahren setzt sich solange fort, bis li genau links neben re steht. Man überlege sich das Ende des Sortierens bei einer Liste mit einer ungeraden Anzahl von Elementen.

Die äußere Schleif wir n/2 mal durchlaufen. Die innere ebenfalls. Dabei gibt es maximal (worst case) vier Vergleiche. A(n) = n/2 * n/2 * 4 und damit ist
A(n) = O(n2).

 

zu 29 Nebenläige Prozesse
29.1 Was ist ein Thread?
zur Startseite www.pohlig.de  (C) MPohlig 2006