Das Aufwandsverhalten von Minsort und Bubblesort

1. am Beispiel von 5 zu sortierenden Zahlen

Es werden 4 Durchläufe benötigt.
Im ersten Durchlauf gibt es 4 Vergleiche, im zweiten 3, im dritten 2 und im vierten Durchlauf 1 Vergleich.

Aufwand:  A(5) = 4+3+2+1 = 10       (Vergleiche)

 

2. allgemein für N zu sortierende Zahlen

Es werden N-1 Durchläufe benötigt.
Im ersten Durchlauf gibt es N-1 Vergleiche ..... und im letzten Durchlauf 1 Vergleich.

Es liegt quadratisches Aufwandsverhalten vor.
Diese beiden Sortieralgorithmen sind deshalb für sehr große Datenmengen uneffektiv.

Berechnen Sie den Aufwand für folgende Datenmengen:

A(10) =
A(100) =
A(1000) =
A(10000) =