OT: slozitost razeni primym zatridovanim

[Miroslav 'Mirco' Bajtos]

> > 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. 
Az si myslim ze to je to co si myslim ;-), tak ano, je to O(n^2)

> Mimochodem quick-sort ma 
> slozitost n*log(n) jen v prumernem pripade, vetsina implementaci 
> pokud radite jiz serazenou posloupnost ma slozitost n^2 !!!:-) 
Da sa to velmi jednoducho obist:
  a) volit pivota nahodne (coz na prvy pohlad znie ako pekna blbost),
     potom pravdepodobnost, ze to bude O(n^2) je hooodne nizka
  b) volit za pivota mediana (t.j. prvok co je mensi ako polovica 
     pola a vacsi ako ta druha), co sa da spocitat v case asi 30*n
     a potom to vyde vzdy O(n.log(n))
  	
> Razeni se zarucenou slozitosti n*log(n) je heap-sort jestli se 
> nepletu (asi zase budu muste juknout do Knutha:-).
Alebo aj napriklad MergeSort a kybel dalsich  ... a mimochodom, ked ta
postupnost neni moc rozhadzana (coz obycajne neni), tak sa to da aj v case
lepsom ako O(n.log(n)). Ale to uz je fakt OT.


					mirco
-- 
i
|     Miroslav 'Mirco' Bajtos  <mirco na centrum.cz>  ICQ: 111299739
|     Student of Charles University in Prague <http://www.cuni.cz>          
:wq