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
= O (n*log n) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Aufgabe 2
Download: |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zu |
29 Nebenläige Prozesse 29.1 Was ist ein Thread? |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2006 |