Beispiel 28

[ksi]

"Sortieren von n Zahlen durch 'Direktes Einfügen'" == Insertion Sort ?

[senenmut]

also, soweit ich gesehen hab: ja "direktes einfügen" ist das gleiche wie insertion sort,
nun bin ich aber ein bisschen verwirrt, worst case für insertion sort is eigentlich eine verkehrt geordnete liste also:
5,4,3,2,1
aber in diesem fall gibt es immer nur einen vergleich pro datenverschiebung(also 5 und 4 werden vergleicht und vertauscht usw)
also müssen wir den worst case für vergleiche anschauen?
also
1,2,3,4,5
da muss jedes element mit den restlichen verglichen werden ( also 1 mit 2 mit 3 mit 4 mit 5; 2 mit 3 mit 4....)

oder steh ich wieder komplett auf der leitung?

*edit:

also ich bekomm für beide O(n^2)

[ksi]

also, soweit ich gesehen hab: ja "direktes einfügen" ist das gleiche wie insertion sort,
nun bin ich aber ein bisschen verwirrt, worst case für insertion sort is eigentlich eine verkehrt geordnete liste also:
5,4,3,2,1
stimmt, hab ich auch so.
aber in diesem fall gibt es immer nur einen vergleich pro datenverschiebung(also 5 und 4 werden vergleicht und vertauscht usw)
in diesem fall gibt es n-1 vergleiche pro durchlauf und n+1 verschiebungen pro durchlauf (jedes wird 1 weitergeschoben, das gerade betrachtete wird auf den ersten platz geschoben (über den umweg einer variablen, deshalb n+1 und nicht n)).
bsp: 4.durchlauf:
3 4 5 [2] 1
2 wird mit 5 verglichen
2 wird mit 4 verglichen
2 wird mit 3 verglichen
=> n-1 = 3 vergleiche.


also müssen wir den worst case für vergleiche anschauen?
also
1,2,3,4,5
das ist der bestcase, in dem fall wird bei jedem durchlauf ja nur ein einziges mal verglichen.
worstcase für vergleiche = worstcase für vertauschungen = 5 4 3 2 1

also ich bekomm für beide O(n^2)
ja, O(n²) passt, bei einer polynomfunktion einfach nur den "hauptterm" nehmen. wenn man sich die formel für O aus dem mathe1-skriptum anschaut, dann is eh auf den ersten blick ersichtlich, dass man da zumindest durch den größten term dividieren muß damit die ungleichung stimmt.

[senenmut]

ok , alles klar danke, mir war nicht ganz klar dass mit wertzuweisungen die "verschiebungen" gemeint waren, also dass es bei v2=1 und w2=3 ist dann ganz klar, also ein vergleich und 3 "verschiebungen"

[Zoidberg]

was ist denn mit der "expliziten Formel" aufsich?
wie muss ich die angeben (falls ich das überhaupt muss)?

[mdk]

was ist denn mit der "expliziten Formel" aufsich?
wie muss ich die angeben (falls ich das überhaupt muss)?

explizite formel = lösung der differenzengleichung.