Hallo zusammen,
in einem Buch habe ich die Aussage gefunden, dass die maximale Anzahl von Datenbewegungen bei insertion_sort n^2/2 beträgt.
Meiner Meinung ist die maximale Anzahl an Datenbewegungen aber:
n^2/2+n/2-1
Beispiel:
4 3 2 1 --> 2 Bewegungen
3 4 2 1 --> 3 Bewegungen
2 3 4 1 --> 4 Bewegungen
1 2 3 4
Wir haben also insgesamt 9 Bewegungen. Laut Buch müssten es aber 8 Bewegungen sein.
Könnt ihr euch das erklären?
Liebe Grüße
da steht, dass die Anzahl der Schritte die Anzahl der Inversionen ist.
Das wären in dem beschriebenen Beispiel dann insgesamt 6:
(4,3)(4,2)(4,1)(3,2)(3,1)(2,1)
Aber was bedeutet das denn dann für meine Frage?
Insgesamt sind dies (n-1) * n / 2 Schritte
nun könnte man aber auch bei n anfangen und nicht bei n-1
also
While-Schleife werden Folgen der Länge 1, 2, 3, …, n durchsucht
dann würde es auch n^2 / 2 werden,
wir nutzen aber
While-Schleife werden Folgen der Länge 1, 2, 3, …, n-1
logic :
man kann davon ausgehen das eigentlich eine zahl garnicht geprüft werden muss (da man ja nur kleiner vergleiche hat und somit der erste (linke) wert automatisch ans ende wandert wenn alle anderen (rechten werte) ihre position (nach links) wechseln , somit landet man dann bei n-1 
und damit ist dann auch deine schrittfolge bei
(n-1) * n / 2
aber genaugenommen sind es maximal
n*n/2
klaro ?
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
mir fällt auch noch ein anders beispiel dafür ein,
mein array
0 1 2 3 4 5 6 7
4 3 2 1 - - - -
ergibt dann
somit muss man die letzte zahl auch noch bewegen
was wiederum dann nicht mit n-1 ist sondern 1 bis n