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

Volker Grabsch vog at notjusthosting.com
Mi Jan 3 17:55:54 CET 2007


On Wed, Jan 03, 2007 at 09:32:02AM +0000, Rocco Rutte wrote:
> * Matthias Kranz [07-01-03 10:12:37 +0100] wrote:
> 
> >Es ist zwar nun fast schon 15 Jahre her und meine Synapsen knallen schon
> >lange nicht mehr so wie früher, aber wenn mich meine grauen Zellen jetzt
> >nicht im Stich lassen (ein Hoch auf den Erschaffer des
> >Langzeitgedächtnisses), dann wollte er vielleicht sagen, dass Quicksort
> >im Worst Case ein O(n^2) und Mergesort O(n*log(n)) braucht?
> 
> Bei mir ist es nicht ganz so lang her: aber nimmt man nicht genau 
> deshalb einen Median

Quicksort mit Median ist natürlich immer optimal. Das folgt direkt aus
der Definition des Median.

Aber die Bestimmung eines Median ist sehr aufwändig. Dein Quicksort
könnte kein O(n*log(n)) mehr erreichen.

Im Gegenteil: Es wäre wahrscheinlich sinnvoller, einen Quicksort oder
Mergesort herzunehmen, um damit den Median zu bestimmen. (Auch wenn's
vielleicht etwas schneller geht, weiß ich im Moment nicht.)

> oder sonstigen Mittelwert bei der Implementierung 
> statt z.B. nur ersten/letzen Wert?

Mir ist nicht klar, was du mit "Mittelwert" meinst.

Meinst du den Wert in der Mitte (an Position array[n/2]), dann ja:
Genau das macht man, damit die Fälle "richtig sortiert" und "entgegen
gesetzt sortiert" keinen Wortcase darstellen. Dennoch kann man
sich ja Datenmengen vorstellen, bei denen die Mitte immer das größte
Element ist (das wäre dann ein sortierter Binärbaum in Infix-Schreibweise).
Den Wort-Case wirst du also nicht los, du drückst ihn nur ins
Unwahrscheinliche.

Meinst du jedoch das arithmetische Mittel aller Elemente: Nicht alle
Daten haben eine Vektorraum-Struktur. Hast du wirklich nur ein
"Compare", und kannst deine Daten-Elemente weder addieren noch skalieren,
dann gibt es einfach keinen Mittelwert.

Doch selbst, wenn wir annehmen, dass du nur Zahlen oder Vektoren
sortierst: Das arithmetische Mittel garantiert ja auch keine
gleichmäßige Aufteilung. Stelle dir 1000 Werte zwischen 0 und 1 vor,
und dann noch ne "1001" dazu. Der Mittelwert wird größer als 1 sein,
und trennt daher nur die "1001" von den anderen 1000 Werten ab. Es
ist im Durchschnitt besser, als einfach den Wert am Index [n/2] zu
nehmen. Aber es fordert von den Eingabedaten mehr als ein "Compare",
und verhindern kann es Worst-Case-Szenarien auch nicht.


Viele Grüße,

    Volker

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



Mehr Informationen über die Mailingliste linux-l