Insertion Sort
-
[quote="drakon"]
(obwohl es eine wirkliche O(nlogn) Variante von Quicksort gibt, die hat aber wegen eine kompilzierten Pivotwahl eine extrem hohe Konstante und wird daher nicht eingesetzt)
Was soll das heissen. ein O( n* log n) mit einer hohen Konstante ist bei
großen Eingabedaten immer noch besser als ein O(n^2) denk ich mal
-
blurry333 schrieb:
drakon schrieb:
(obwohl es eine wirkliche O(nlogn) Variante von Quicksort gibt, die hat aber wegen eine kompilzierten Pivotwahl eine extrem hohe Konstante und wird daher nicht eingesetzt)
Was soll das heissen. ein O( n* log n) mit einer hohen Konstante ist bei
großen Eingabedaten immer noch besser als ein O(n^2) denk ich malJa, aber es müssen seeehr grosse Eingabemengen sein. So gross (ich kann keine Zahlen nennen), dass es nicht real ist. Im übrigen haben wir ja gute O(nlogn) Sortieralgorithmen wie Mergesort oder Heapsort, welche bessere Konstanten haben als die Quicksort Variante.
-
von welcher Konstante sprichst du ?
Muss ja sehr groß seinalso meine obige konstante 1.5 muss stimmen.
ist sie beim heapsort wohl < 1
-
blurry333 schrieb:
tatsächlich:
Hab hier 2 Formel für den average case:
Quicksort: 1.5 * (n*log n)
Selection Sort : 0.25 * n^2 .bei n=8 z.B. ist selection sort besser.
Frag mich grad wo die Grenze ist. z.B. n=100 ist quicksort besser
Ich hoffe mal, dein log ist ein ld.
Also 1.5 * (n*log n) = 0.25 * n^2
Dann sagt der Taschenrechner n=1.148
edit: Taschenrechner (fx-991ES) kann's nicht.Deine Formeln sind mir unheimlich. Und dran glauben tue ich auch nicht.
Die Grenze, ab der man Insertion Sort statt Quicksort nehmen sollte, kann man nicht allgemein sagen. Aber wenn sie zwischen 20 und 50 legt, ist man gut dabei.
Selection Sort nimmt man nicht.
-
ähm setz doch mal n=8 ein. Dann siehst du das Selection sort besser ist.
Die grenze muss über 8 sein .
Ja zur Basis 2
Zitat:
Selection Sort nimmt man nicht.
Warum ? Man hat wenig Kopierarbeit
-
Die Grenze liegt wohl bei 30
hab ich jetzt mal probiert. Keine Ahnung wie man das mathematisch macht.
-
blurry333 schrieb:
von welcher Konstante sprichst du ?
Muss ja sehr groß sein
also meine obige konstante 1.5 muss stimmen.
ist sie beim heapsort wohl < 1´Mal rechnen. Die Konstante nenne ich k.
k*n*ln(n)=n^2 |/n
k*ld(n)=n
k=n/ln(n)Die Formel kenne ich doch irgendwoher...
Oh, wenn man k hat, muß man sich nur die k-te Primzahl suchen und weiß ungefähr, ab welchem n Quicksort schneller ist.
k=1000000 => n=16626508,9 (das hier kann der Taschenrechner komischerweise wieder)
Kann jemand zum Vergleich mal die millionste Primzahl rausfinden und danebenstellen?
-
Zwischenstand:
0,89= 1/n * 2^n
wie löst man das ??
ups das kann nicht stimmen.
-
Weit komme ich auch nicht.
1.5 * n * ld(n) = 0.25 * n^2
6 * n * ld(n) = n^2
6 * n * ln(n)/ln(2) = n^2
6 * ln(n)/ln(2) = n
6/ln(2) = n/ln(n)Riecht nach http://de.wikipedia.org/wiki/Lambertsche_W-Funktion
Aber mit der bin ich total ungeübt.
Und jetzt sagt der Taschenrechner n=29.21048705, durch das Umformen ist es für ihn wohl einfacher geworden.
1.5 * n * ld(n) = 213.31
0.25 * n^2 = 213.31
Ok, stimmt.
-
Für sowas ist wolframalpha praktisch: http://www.wolframalpha.com/input/?i=6%2Fln(2)+%3D+n%2Fln(n)+