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