[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

[Volker Grabsch]

On Wed, Jan 03, 2007 at 07:11:23AM +0000, Rocco Rutte wrote:
> * Volker Grabsch [07-01-03 04:53:34 +0100] wrote:
> >On Tue, Jan 02, 2007 at 10:11:37PM +0100, Oliver Bandel wrote:
> >>die Frage ist für Leute, die sich mit Algorithmen und
> >>Parallelisierung auskennen:
> 
> >>Kann man einen Sort parallelisieren und dadurch Rechenzeit sparen?
> 
> >Ja. siehe Merge-Sort.
> 
> >Das ist nicht nur der zuerst auf Computern implementierte, sondern
> >auch der bislang schnellste und beste.
> 
> Wieso ist MergeSort im Vergleich zu QuickSort schneller und besser? 
> Beide gehören zur selben Klasse, für man zeigen kann, dass es nicht mehr 
> schneller geht (die Komplexität, nicht die Implementierung).

Ja, bei beiden liegt die durchschnittliche Sortierzeit in O(n*log(n)).

Bei Quicksort jedoch kann es im Extremfall auch O(n^2) werden, wenn
die Pivot-Elemente dumm gewählt sind (weiß man ja vorher nicht). Dann
degeneriert Quicksort zum Bubblesort.

Bei Mergesort hingegen dauert es immer gleich lang, egal wie die
Elemente vorher sortiert waren.

Auch wenn Quicksort bekannter ist und häufiger eingesetzt wird, hat
das doch eher was mit den Datenstrukturen zu tun (Arrays in C/Fortran/...).
Verwendet man hingegen verkettete Listen, in funktionalen Sprachen
etwas ganz Natürliches, dann ist auf jeden Fall Mergesort das Mittel
der Wahl.

Da beim Parallelisieren ohnehin die Daten vom einen Rechner zum anderen
müssen, ist eine Sortierung am Platz aber eh nicht mehr sinnvoll. Daher
lautete meine Empfehlung Mergesort, weil die wenigen Vorteile von
Quicksort überhaupt nicht zum Tragen kommen.


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR