Insertion Sort
-
blurry333 schrieb:
Ich les da grad was von Sentinel Schlüssel der mindestens so klein
wie das kleinste Element sein soll.Das ist jetzt nicht dein Ernst, oder?
-
ich muss den kleinsten Wert im array ja erst mal suchen oder.
und a[0] den kleinsten Wert im array zuweisen
-
in wikipedia steht der Insertion Sort soll bei ziemlich kleinen
Eingabenmengen effizient sein. Ich seh jetzt eigentlich nur den vorteil
bei vorsortierten Eingabedaten. hmm...
-
blurry333 schrieb:
in wikipedia steht der Insertion Sort soll bei ziemlich kleinen
Eingabenmengen effizient sein. Ich seh jetzt eigentlich nur den vorteil
bei vorsortierten Eingabedaten. hmm...Ist das eine Frage oder eine Feststellung?
Insertion Sort ist bei kleinen Eingabemengen effizient, weil es sehr sehr einfach aufgebaut ist. Du hast ja neulich schonmal so viele Fragen zur Leufzeitanalyse gestellt (das warst doch du, oder erinnere ich mich falsch?). Insertion Sort ist zwar O(n²), aber da es so einfach aufgbaut ist, ist der Vorfaktor vor dem O(n²) meistens sehr viel kleiner als bei den viel komplexer arbeitenden O(n*log(n))-Algorithmen. Das geht sogar so weit, dass gute Implementierungen der O(n*log(n))-Algorithmen Quicksort oder Mergesort ein Insertion Sort für kleine Eingabemengen benutzen (Quicksort und Mergesort teilen grob gesagt die Eingabemenge rekursiv in immer kleinere Teilmengen auf, die dann sortiert werden. Ab einer gewissen Größe wird dazu zu Insertion Sort gewechselt, anstatt am Ende einelementige Mengen zu "sortieren").
-
Das geht sogar so weit, dass gute Implementierungen der O(n*log(n))-Algorithmen Quicksort oder Mergesort
Quicksort ist nicht in O(nlogn), sondern O(n^2). Diese blöde Pivotwahl macht alles kaputt.
(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)
-
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
-
[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)+
