Fehler im Repetitorium?

  • Worstcase = Feld ist aufsteigend sortiert


    Bei der Implementierung von Quicksort so wie sie im Skriptum ist, ist die Anzahl der Datenbewegungen Theta(n ) aber die Anzahl der Vergleiche ist Theta(n^2) (steht über dem Absatz mit dem Hinweis - Augen aufmachen ;) )

  • noch was:
    der insertion sorf müsste ja eigentlich Theta(n²) Schlüsselbewegungen haben, oder? (die größeren elemente rutschen ja alle ein stück nach rechts, wenn ein neues vom unsortierten teil reinsortiert wird)

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  • Zitat

    Original geschrieben von steve
    noch was:
    der insertion sorf müsste ja eigentlich Theta(n²) Schlüsselbewegungen haben, oder? (die größeren elemente rutschen ja alle ein stück nach rechts, wenn ein neues vom unsortierten teil reinsortiert wird)


    im worstcase schon ( absteigend sortiert ), im bestcase isa linear ( Folge bereits aufsteigend sortiert ).

  • naujo, ich bin einmal vom average ausgegangen, und der ist ja irgendwo dazwischen (wohl eher beim n², oder?)

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .