Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Bubblesort 3)
 

 
 



















 

Für die  Aufwandsanalyse orientieren wir uns am  C-Programm.

 Schlüsselvergleiche:
  • Die i-Schleife wird  (n-1)-mal durchlaufen.
  • Beim i-ten Durchlauf wird die j-Schleife (n - (i+1)) =  (n-i-1)-mal durchlaufen.
  • Dabei erfolgt jeweils  ein Schlüsselvergleich.
Also:


 Umspeicherungen:
  • Die i-Schleife wird  (n-1)-mal durchlaufen.
  • Die j-Schleife wird  (n-i-1)-mal aufgerufen.
  • Der if-Zweig innerhalb der j-Schleife wird dabei
       

    • im besten Fall nie
    • im schlechtesten Fall immer
    • im Mittel jedes zweite Mal
    durchlaufen. Dabei erfolgen jeweils  drei Umspeicherungen.
Also:
    0  

 
Seite 11/17