Matematické Fórum

Předělal bych to na nerekurzivní. Počet rekurzí se odvíjí od objemu dat a jelikož vyvíjíš framework, nemůžeš předem říci jaké aplikace na frameworku budou běžet a jak velký budou mít vstup.


Můžeš prozradit o jakou platformu se jedná?


Přímo k tomu quicksortu, nechci kecat, klidně mě opravte, ale vidím to nějak takhle:
Průběh Quicksortu se dá zaznamenat binárním stromem (máš celý vstup, rozdělí se podle pivota na 2 atd...)
V každém zpracování jednoho dílu se tedy rekurze zavolá 2x. Zaříznutí rekurze u ideálního bin. stromu log(n)

Představ si nejhorší případ, tedy že vždy vybereš pivota tak, že rozdělíš pole na 1 a n - 1 prvků... to pak bude vypadat graf takhle:


Z čehož je vidět že jeho hloubka bude n/2 což je v podstatě lineární ke vstupu. A hloubka je zaříznutí rekurze, takže v nejhorším případě můžeš srovnat max. 400 čísel pokud to bereš doslovně, asymptoticky 200.

Což moc není, záleží pro co ten framework vyvíjíš. Ale znovu říkám, mohu se plést.

U quicksortu se neda matematicky odhadnout hloubka rekurze, protoze zavisi na vstupnich datech. Sice v prumernem pripade to bude cca logaritmicka hloubka, tak je i pripad, co psal jindra, kdy to bude mit linearni hloubku.

Ale treba u mergesortu uz se ta hloubka odhadnout da, tam je to vzdycky logaritmicky...

Jinak me by teda prislo nejlepsi si hlidat, jak jsi hluboko a pokud uz se budes u tech 200, tak tam na ten zbytek pustit treba nerekurzivni insert sort. Ono to je i u nekterych implementaci quicksortu udelane tak, ze na useky kratsi nez je nejaka dana hranice se pak pouzije nerekurzivni algoritmus, protoze je to rychlejsi.