Třídící algoritmy v praxi Vyřešeno

[denethor]

Ahoj
snažím se setřídit pole, které bude mít maximálně tak 10000 prvků. Zatím používám mergesort, to funguje, ale chtěl bych, aby to běhalo rychleji. Nevíte někdo, jestli treba quicksort bude rychlejší a o kolik přibližně? Asymptotická složitost je pořád nlogn, ale myslím, že merge je dost složitý a proto pomalejší... Nebo jaký algoritmus byste použili vy?
Dik

[Reklama]

[Koja]

Quicksort patří mezi nejrychlejší (stejně jako mergesort a heapsort), ale hodně záleží na způsobu jeho implementace. Pokud to uděláš špatně, tak bude o poznání pomalejší. Z těch dalších bych vyzkoušel i heapsort.

[Tomina]

QuickSort bývá u větších polí nestabilní, ovšem je nejrychlejší. Řazení haldou je na tom podobně, jak QuickSort, čili tam ten smysl moc nevidím. Nic jiného snad není, klasická bublinovka je jen na menší pole.

Počítal sis časovou složitost svého algoritmu?

[Koja]

Velikost pole nemá na (ne)stabilitu až takový vliv. A zároveň by vůbec nemuselo vadit, že je nestabilní, záleží na tom, co přesně chce řadit.

[denethor]

Dik za odpovědi.

Nemáte představu, kolikrát by asi byl dobře naprogramovaný quicksort rychlejší než mergesort? Jestli je třeba možný mít dvojnásobný zrychlení? Protože se mi to nechce jen tak zkoušet a pak to vyjde skoro nastejno.

Jestli je časová složitost to, co si myslim, že to je, tak mam nlogn, což je asi nejlepsi mozne.

A o to, jestli je algoritmus stabilni nebo ne nejde.

[Koja]

2x rychlejší rozhodně nebude. Podívej se sem, nastav si problem size na 50, a uvidíš, že merge je mírně rychlejší, než quick. Zároveň quick sice má obvykle složitost "nlogn", ale v nejhorších případech může mít až kvadratickou (n^2).