32.3 Abschätzungen für die
Sortieralgorithmen |
||||||||||
BubbleSort |
Um den Aufwand beim BubbleSort
abschätzen zu können, schauen wir uns noch einmal die Implementierung der
Methode an. Der Erste Eintrag in der Liste wird mit alle anderen
Einträgen in der Liste verglichen, somit wir haben n-1 Vergleiche. Das zweite Glied mit dem Rest
also n-2 Vergleiche, usw. Wir haben also insgesamt
(n-1) + (n-2) + (n-3) + .. + 1 = (n-1)(n-2)/2 Vergleiche. Somit ist der Aufwand O(n2). Analog kann man begründen dass auch die Anzahl der Vertauschungen (worst case) eine Funktion O(n2) ist.
Aufwand: O(n2)
|
|||||||||
Einfügen |
Auch hier ist leicht einzusehen, dass die Anzahl der Vergleiche (worst case) 1 + 2 + 3 + ... + n-1 =
(n-1)(n-2)/2 = O(n2) ist. Ebenso sind die Anzahl der möglichen
Vertauschungen (wieder worst case) 1 + 2 + 3 + ... + n-1 = Aufwand: O(n2)
|
|||||||||
QuickSort |
Der Aufwand wird bestimmt durch die
rekursive Methode
Wir haben beim ersten Aufruf n-1 Vergleich in der do-while Schleife. Nehmen wir an, dass die Elemente so verteilt sind, dass das Aufteilen in Teillisten durch das pivot-Element immer wieder gleich große Listen erzeugt (nicht worst case), so können wir für den Aufwand A(n) sagen.
|
|||||||||
Für das Vertauschen gilt das gleiche. | ||||||||||
Aufwand: O(n* log n) |
||||||||||
Vergleiche: | O(n*log n) | |||||||||
: | Verschiebeoperationen: | O(n*öog n) | ||||||||
zu | 32.4 Übungen | |||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |