Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Sortieren durch Auswahl 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.
Die Gesamtzahl der Schlüsselvergleiche ist also unabhängig von den Schlüsseln der Datensätze:



 Umspeicherungen:
  • Die i-Schleife wird  (n-1)-mal durchlaufen.
  • Pro Durchlauf der i-Schleife werden  4 Umspeicherungen durchgeführt (zzgl. denen der j-Schleife).
  • 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 erfolgt jeweils  eine Umspeicherung, also insgesamt
       


    • im besten Fall 0
    • im schlechtesten Fall n-1-i
    • im Mittel (n-1-i)/2
    Umspeicherungen.
Also:
 
Seite 8/17