3 Zahlen sortieren?
-
Was ist der optimale (Pseudo-)Code, um 3 Zahlen zu sortieren?
-
Analoge Frage für 4 Zahlen.
-
Für 3 Zahlen habe ich folgendes gefunden:
swap_if(c < a, a, c) swap_if(b < a, a, b) swap_if(c < b, c, b)
-
Für 4 Zahlen:
swap_if(d < a, a, d) swap_if(c < a, a, c) swap_if(b < a, a, b) // jetzt ist a die kleinste Zahl // dann den Code für 3 Zahlen anwenden auf b,c,d [= 3 swap_if's]also 6 swap_if's. Geht's auch besser?
-
Es geht wohl mit 5 Vergleichen: http://stackoverflow.com/questions/6145364/sort-4-number-with-few-comparisons
-
Relevanter Link, damit wir nicht sämtliche Zahlen durchkauen müssen:
http://pages.ripco.net/~jgamble/nw.html
-
Vergleiche!? Ich seh' das meist auf den ersten Blick ...
-
sdffd schrieb:
Für 3 Zahlen habe ich folgendes gefunden:
swap_if(c < a, a, c) swap_if(b < a, a, b) swap_if(c < b, c, b)einen funken besser wenn es keine spezialhardware fuer swap_if gibt
swap_if(b < a, a, b) if(c<b) { std::swap(b,c); swap_if(b < a, a, b) }manchmal ist das nett:
sum=a+b+c; A=min(a,b,c); C=max(a,b,c); B=sum-A-C;kommt auf die definition von "optimal" und die hardware an
-
Kann man eigentlich mit C++14 und Variadic Templates die optimale Sortierfunktion für n Elemente implementieren?
-
fdgfd schrieb:
Kann man eigentlich mit C++14 und Variadic Templates die optimale Sortierfunktion für n Elemente implementieren?
Ja.
-
yesonecan schrieb:
fdgfd schrieb:
Kann man eigentlich mit C++14 und Variadic Templates die optimale Sortierfunktion für n Elemente implementieren?
Ja.
thx sieht ja 1337 aus. Ist das von dir?
-
fdgfd schrieb:
yesonecan schrieb:
fdgfd schrieb:
Kann man eigentlich mit C++14 und Variadic Templates die optimale Sortierfunktion für n Elemente implementieren?
Ja.
thx sieht ja 1337 aus. Ist das von dir?
Der Code ist von mir, aber ich habe eigentlich nur https://en.wikipedia.org/wiki/Batcher_odd–even_mergesort 1:1 in C++ übersetzt.
-
und wird das wirklich in eine statische Abfolge von "swap_if"s übersetzt?
-
-
