Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Sortieren durch Einfügen 3)
 

 
 





















































 

Für die  Aufwandsanalyse orientieren wir uns am  C-Programm.
Wir zählen Schlüsselvergleiche V und (Datensatz-) Umspeicherungen U.

 Schlüsselvergleiche:

Im besten Fall sind die Datensätze bereits sortiert.
  • Dann wird die i-Schleife (wie in allen anderen Fällen auch) genau  (n-1)-mal durchlaufen.
  • In jedem Durchlauf wird  ein Schlüsselvergleich durchgeführt,
    der if-Zweig wird aber nie durchlaufen.
Also:



Im schlechtesten Fall wird der if-Zweig in jedem Durchlauf der i-Schleife durchlaufen.
  • Dann wird die i-Schleife (wie in allen anderen Fällen auch) genau  (n-1)-mal durchlaufen.
  • In jedem Durchlauf wird  ein Schlüsselvergleich durchgeführt,
    der if-Zweig wird jedesmal durchlaufen.
  • Im if-Zweig wird eine do-while-Schleife durchgeführt.
    Diese wird (im schlechtesten Fall)  i-mal durchlaufen.
  • Jeder Durchlauf erfordert dabei  einen Schlüsselvergleich.
Also:


Im Mittel wird
  • die i-Schleife wieder genau  (n-1)-mal durchlaufen.
  • In jedem Durchlauf wird  ein Schlüsselvergleich durchgeführt.
    Der if-Zweig wird in jedem Durchlauf der i-Schleife 0.5-mal durchlaufen
    (d.h. bei der Häfte der Durchläufe wird der if-Zweig durchlaufen).
  • Die do-while-Schleife innerhalb des if-Zweigs wird also  (i+1)/2-mal durchlaufen.
  • Jeder Durchlauf erfordert dabei  einen Schlüsselvergleich.
Also:


 Umspeicherungen:

Im besten Fall sind die Datensätze bereits sortiert, d.h.
  • in der i-Schleife sind  keine Umspeicherungen notwendig.
Also:
0


Im schlechtesten Fall wird
  • in jedem der  n-1 Durchläufe der i-Schleife der if-Zweig einmal durchlaufen.
  • Im if-Zweig werden  zwei Umspeicherungen und eine do-while-Schleife durchgeführt.
  • Die do-while-Schleife wird (im schlechtesten Fall)  i-mal durchlaufen.
  • Jeder Durchlauf erfordert dabei  eine Umspeicherung.
Also:



Im Mittel wird
  • in jedem der n-1 Durchläufe der i-Schleife der if-Zweig  0.5-mal durchlaufen
    (d.h. bei der Häfte der Durchläufe wird der if-Zweig durchlaufen).
  • Im if-Zweig werden  zwei Umspeicherungen und eine do-while-Schleife durchgeführt.
  • Die do-while-Schleife wird im Mittel  (i+1)/2-mal durchlaufen.
  • Jeder Durchlauf erfordert dabei  eine Umspeicherung.
Also:
 
Seite 5/17