| | |
| Titel: | Sortieralgorithmen | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Bubble Sort (Sortieren durch Austauschen)
Beschreibung
- Die Daten werden in einer doppelten Schleife abgearbeitet.
- Die innere Schleife umspannt jeweils den gesamten unsortierten Bereich: Dieser wird iterativ durchgearbeitet. Wenn ein Element größer ist als sein rechter Nachbar, so werden sie miteinander vertauscht.
- Nach jedem äußeren Schleifendurchlauf wurde der sortierte Bereich am Ende der Daten um mindestens 1 erhöht.
Programmcode
procedure BubbleSort ( var f :
TArray; HighIndex : integer ) : string;
var i, j :
integer;
begin
for i := HighIndex downto 1
// äußere Schleife
do for j := 0 to
i
do if f[j] > f[j+1] then
swap (f[j], f[j+1]); // innere Schleife
end; //
BubbleSort
Aufwandsabschätzung
mittlerer-Aufwand:
- Die äußere Schleife wird n-1 mal durchlaufen.
- Die innere Schleife wird im Durchschnitt (n-1)/2 mal durchlaufen.
Daraus folgt der Aufwand
.
.Der maximale Aufwand beträgt ebenfalls O(n2), da beide
Schleifen auch im schlechtesten Fall genauso oft durchlaufen werden. Der
Unterschied ist nur die Anzahl der benötigten Tauschvorgänge (im
besten Fall ist gar keiner nötig).
Zurück zu Themenseiten:
StudyPaper.com/Startseite/Computer/Informatik
StudyPaper.com/Startseite/Wissenschaft/Wirtschaftswissenschaften
StudyPaper.com/Startseite
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
