(Klausurfrage) Geben sie eine Möglichkeit an Quicksort schneller zu machen.

Hi,

wie kann man Quicksort schneller machen? Ich hätte vermutet irgendwie mit Threads aber k.A. Weiß irgendjemand eine Möglichkeit?

mfg

volkard

WhoIsWho schrieb:

Hi,
wie kann man Quicksort schneller machen? Ich hätte vermutet irgendwie mit Threads aber k.A. Weiß irgendjemand eine Möglichkeit?
mfg

Viele viele Möglicheiten. Aber ich nehme an, er hatte ein konkretes Quicksort im Sinn, un das müßtest Du uns schon zeigen.

SideWinder

Ich glaub die wollen immer diese Standardantwort mit der Wahl des Pivotelements.

MfG SideWinder

Hi,

es war kein Code angegeben. Es bezog sich wahrscheinlich auf den Algorithmus wie er im allg. vorgestellt also mit Pseudocode wie z.B. in "Introduction to Algorithms"

volkard

SideWinder schrieb:

Ich glaub die wollen immer diese Standardantwort mit der Wahl des Pivotelements.
MfG SideWinder

Ah, da den second-of-five nehmen, um bei einigermaßen vorsortierten Teilfeldern weniger falschvorhergesagte Sprünge zu haben und trotz mehr Schritten weniger Zeit zu verbraten. Klingt interessant.
Oder klassich den media-of-three, aber macht das echt schneller? Ich dachte, das macht nur vorsortierte Felder schneller.
Da würde ich schon eher vorschlagen, die Rekursion nicht bis unten hingehen zu lassen, sondern nur bis (je nach Rechner) 32-große Subarrays und am Schluß mit einem insertionsort drüberzuhuschen (eins am Ende ist noch besser, als unten lauter kleine insertionsorts zu machen).

Blue-Tiger

volkard schrieb:

SideWinder schrieb:

Ich glaub die wollen immer diese Standardantwort mit der Wahl des Pivotelements.
MfG SideWinder

Ah, da den second-of-five nehmen, um bei einigermaßen vorsortierten Teilfeldern weniger falschvorhergesagte Sprünge zu haben und trotz mehr Schritten weniger Zeit zu verbraten. Klingt interessant.

Was ist der second-of-five, und was sind die Vorteile ggue. median-of-three? Ich hab das noch nie gehoert und Google spuckt auch nix aus

nman

Naja, das alte Zeugs von wegen Wahl des Pivot-Elements und so.
Gibt da ein paar solche Klassiker, die in jedem Algorithmen&Datenstrukturen-Skriptum bzw. -Buch beschrieben werden.

hustbaer

Nimmt man nicht eher den "median of three medians of three"?
Hab zumindest mal so eine Implementierung gesehen, wenns nicht sogar die in der MSVC Standard-Library war.

@Blue-Tiger: Ich nehme an dass der "second of five" der "links" neben dem "median of five" ist, wenn ich das mal so salopp formulieren darf
(wobei "links" oder "rechts" natürlich egal ist)

volkard

Blue-Tiger schrieb:

Ich hab das noch nie gehoert

Ich auch nicht. Das ist evtl auch noch nie implementiert worden, und ob's was bringt, weiß ich auch nicht.

volkard

hustbaer schrieb:

Nimmt man nicht eher den "median of three medians of three"?
Hab zumindest mal so eine Implementierung gesehen, wenns nicht sogar die in der MSVC Standard-Library war.

http://www.inference.phy.cam.ac.uk/mackay/sorting/sorting.html sagt, "Summary: 'median-of-3' is a good idea, but even better (for all N greater than 70 or so) is 'median-of-sqrt(N/log(N))'."

hustbaer

@volkard: ich rede davon was gängige Parxis ist, nicht davon was eine Schlaue Idee wäre, aber kaum jemals jemand implementiert.

volkard

hustbaer schrieb:

@volkard: ich rede davon was gängige Parxis ist, nicht davon was eine Schlaue Idee wäre, aber kaum jemals jemand implementiert.

Sowas wie std::sort besteht aus vielen inenandergreifenden Entscheidungen, welche Pivotwahl, welcher Abbruch von Introsort, welche Abbruch nach unten, unten Stückchenweise oder auf einmal, welche alternative gegen den worst case, tail recursion optimieren, wieviel code mit unguarded Version anbieten oder gar Sentinels selber setzen? Wenn ich ausmesse, daß ich unten bei Größen von 50 abbrechen sollte, und woanders lese, daß der median-of-three ab 70 fraglich wird, kann ich schon auf die Idee kommen, gleich mal prophylaktisch mehr als 3 Elemente anzuschauen. Das letze mal, daß ich beim MSVC gelesen habe, war es nur median-of-three. Bei GCC heute auch. median-of-three-medians-of-three habe ich noch nie gelesen.

hustbaer

volkard schrieb:

hustbaer schrieb:

@volkard: ich rede davon was gängige Parxis ist, nicht davon was eine Schlaue Idee wäre, aber kaum jemals jemand implementiert.

(...)
median-of-three-medians-of-three habe ich noch nie gelesen.

Ok, das ist eine Antwort in der Art wie ich sie haben wollte
Danke.

p.S.:
Hab grad mal eben nachgesehen (MSVC 2005, weil ich den grad offen hatte)

// MSVC 2005 Standard Library:

template<class _RanIt,
	class _Pr> inline
	void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
	{	// sort median element to middle
	if (40 < _Last - _First)
		{	// median of nine
		size_t _Step = (_Last - _First + 1) / 8;
		_Med3(_First, _First + _Step, _First + 2 * _Step, _Pred);
		_Med3(_Mid - _Step, _Mid, _Mid + _Step, _Pred);
		_Med3(_Last - 2 * _Step, _Last - _Step, _Last, _Pred);
		_Med3(_First + _Step, _Mid, _Last - _Step, _Pred);
		}
	else
		_Med3(_First, _Mid, _Last, _Pred);
	}

Das oben fälschlicherweise mit "median of nine" kommentierte ist der von mir erwähnte "median of three medians of three".