Insertion Sort

blurry333

IM Algorithmen Buch von Robert Sedgewick stehts aber genauso drin.
Es scheint trotzdem so zu funktionieren. Vielleicht bricht er bei einem
negativen Index automatisch ab. Ich hab keine Ahnung

padreigh

blurry333 schrieb:

// snip code
die 2.Schleife funktioniert auch ohne die Prüfung ob j>0 ist.
Wie kann das sein. Zufall ?? auf alle Fälle wird geprüft ob
arr[-1] also mit negativen Index wenn ich die Prüfung auf j>0 weglasse.

Und?

for(int i=1;i<length;i++)
	 {
		 tmp=arr[i];j=i;

i fängt bei 1 an, j = i ; Also wird j minimaler Weise 0 ... wo ist das Problem?

Michael E.

Vielleicht solltest du noch eine Seite weiterlesen im Buch:

Es muß noch eine wichtige Einzelheit betrachtet werden: Für die meisten Eingaben funktioniert die Prozedur insertion nicht! Die while-Anweisung läuft über dsa linke Ende des Feldes hinaus, wenn v [bei dir temp] das kleinste Element im Feld ist. Um Abhilfe zu schaffen, setzen wir einen "Marken"-Schlüssel ("sentinel"-key") auf a[0], den wir mindestens so klein wählen wie das kleinste Element im Feld. Marken werden gewöhnlich in Situationen wie dieser verwendet, um die Aufnahme eines nahezu immer positiv ausfallenden Tests (im vorliegenden Falle j > 1) in die innere Schleife zu vermeiden.

Michael E.

padreigh schrieb:

i fängt bei 1 an, j = i ; Also wird j minimaler Weise 0 ... wo ist das Problem?

Beim j--, siehe innere Schleife.

blurry333

void insertionsort(char* arr,int length) 
 { 
     int j,i;char tmp; 

     for(int i=1;i<length;i++) 
     { 
         tmp=arr[i];j=i; 

         for(j;tmp<arr[j-1];j--)  //j wird runtergezählt   
             arr[j]=arr[j-1];    // j kann theoretisch unendlich klein sein     

         arr[j]=tmp; 
     } 
}

blurry333

wie würde denn der Code mit Sentinel aussehen ?

Ich les da grad was von Sentinel Schlüssel der mindestens so klein
wie das kleinste Element sein soll.

Michael E.

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?

blurry333

ich muss den kleinsten Wert im array ja erst mal suchen oder.

und a[0] den kleinsten Wert im array zuweisen

blurry333

in wikipedia steht der Insertion Sort soll bei ziemlich kleinen
Eingabenmengen effizient sein. Ich seh jetzt eigentlich nur den vorteil
bei vorsortierten Eingabedaten. hmm...

SeppJ

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").

drakon

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)

blurry333

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

blurry333

[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

drakon

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 mal

Ja, 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.

blurry333

von welcher Konstante sprichst du ?
Muss ja sehr groß sein

also meine obige konstante 1.5 muss stimmen.

ist sie beim heapsort wohl < 1

volkard

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.

blurry333

ä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

blurry333

Die Grenze liegt wohl bei 30
hab ich jetzt mal probiert. Keine Ahnung wie man das mathematisch macht.

volkard

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?

blurry333

Zwischenstand:

0,89= 1/n * 2^n

wie löst man das ??

ups das kann nicht stimmen.