Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:



Podkopávání algoritmu quicksort

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: Podkopávání algoritmu quicksort

Autor: zdfvgsdfgsdfg ♂

12:21:37 20.01.2013

Petr Zakopal napsal/a

Dobrý den,
snažím se vymyslet takové řady, které budou těžko zpracovatelné pro algoritmus quicksort. Vymyslel jsem několik příkladů řad. Prosím podívejte se na ně a napište mi, zda si myslíte, že by s nimi měl quicksort problém. Používám algoritmus A. C. Hoare, takže pivot je vždy ve středu.
řady:
1) 1 000 -> 0 -> 1 000
2) 1 000 -> sudá čísla -> 0 -> lichá čísla -> 1 000
3) 10 -> 0 -> 10 -> 0 ->10-> ............ 10 -> 0 -> 10 -> 0 ->10
napadají vás nějaké další řady čísel, které by mohly podlamovat princi quicksortu? pokud ano tak mi je prosím napište a také prosím ohodnoťte tyto 3 co jsem napsal. Děkuji




Jeho průměrná časová složitost je pro algoritmy této skupiny nejlepší možná (O(N log2 N)), v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N^2).

Největším problémem celého algoritmu je volba pivotu. Pokud se daří volit číslo blízké mediánu řazené části pole, je algoritmus skutečně velmi rychlý. V opačném případě se jeho časová složitost blíží O(N^2).

http://cs.wikipedia.org/wiki/Quicksort

Citovat příspěvek

 

Podkopávání algoritmu quicksort

Autor: Petr Zakopal ♂

22:44:17 19.01.2013

Dobrý den,
snažím se vymyslet takové řady, které budou těžko zpracovatelné pro algoritmus quicksort. Vymyslel jsem několik příkladů řad. Prosím podívejte se na ně a napište mi, zda si myslíte, že by s nimi měl quicksort problém. Používám algoritmus A. C. Hoare, takže pivot je vždy ve středu.
řady:
1) 1 000 -> 0 -> 1 000
2) 1 000 -> sudá čísla -> 0 -> lichá čísla -> 1 000
3) 10 -> 0 -> 10 -> 0 ->10-> ............ 10 -> 0 -> 10 -> 0 ->10
napadají vás nějaké další řady čísel, které by mohly podlamovat princi quicksortu? pokud ano tak mi je prosím napište a také prosím ohodnoťte tyto 3 co jsem napsal. Děkuji

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: