quicksort

[Nagy Endre]

> > hatekony, csak ha n db processzoron szamolod parhuzamositva, hogy az adott
> > processzorhoz tartozo tombelemnel hany kisebb van a tombben. Annyiadik
>
> Tenyleg, tudsz erre alkalmazast? Nyilvan igazad van valtozo
> ertekkeszletre, de hirtelen semmi sem jut eszembe, amiben viszonylag kis
> tombok rendezesere (tobb 10k nyilvan nem megy igy) ennyi proci van.

Pont erre ne lenne mainframe-en Assembly utasitas? :)

De amugy eleg trivialis az alkalmazasa: egyszerre annyi adatot veszunk,
amennyihez van eleg parhuzamos szamitasi kapacitas (siman lehet tobb
10k, ehhez nem kell feltetlenul ugyanennyi processzor), aztan a vegen a
rendezett tombcsoportokra nyomunk mergesortokat.

De vannak ennel sokkal hatekonyabb parhuzamos rendezesek is. Amennyire
tudom, a legjobbak O(log n) nagysagrendben vannak, n^(4/3) processzoron.

Gumo