OT: slozitost razeni primym zatridovanim

[AdaMcPetr]

> Dobry den,
> kolega ma problem, potrebuje vedet, jakou slozitost ma razeni
> zatridovanim, muzete mu nekdo pomoci?
> Vime, ze je to lepsi nez bubble-sort (n^2) a horsi nez quick-sort
> (n*log(n))...
Domnivam se ze razeni zatridovanim ma stejnou (tj. n^2) slozitost 
jako bubble-sort, to ze je rychlejsi je dano tim, ze implementace 
nejspis pouziva vice pameti (takze se nepresouva tolik dat), proste 
ke jen konstatna-krat rychlejsi. Mimochodem quick-sort ma 
slozitost n*log(n) jen v prumernem pripade, vetsina implementaci 
pokud radite jiz serazenou posloupnost ma slozitost n^2 !!!:-) 
Razeni se zarucenou slozitosti n*log(n) je heap-sort jestli se 
nepletu (asi zase budu muste juknout do Knutha:-).
AdaMcPetr
petr.adamek na antek.cz
http://www.antek.cz