Sortier-Algorithmus, Insertionsort - Was ist eine Recordbewegung?

...komplette Frage anzeigen

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Genaugenommen klingt das nach Denglisch, also record ist english für Eintrag und mit record bewegung, meinen die vermutlich die Anzahl der Vertauschungen die nötig sind bis das Feld (Array) sortiert ist.
Man unterscheidet bei Vergleichsbasierten Sortieralgorithmen nämlich zwischen Anzahl der Vergleiche und Anzahl der Vertauschungen, weil auf vielen Rechnerarchitekturen ein Vergleich schneller geht, als eine Vertauschung, deswegen wirkt sich beides unterschiedlich auf die Laufzeit aus.
Also Laufzeit ist ungefähr gleich (Anzahl der Vergleiche * Zeit pro Vergleich) + (Anzahl der Vertauschungen * Zeit pro Tausch)
Die Formulierung 'Recordbewegung' ist sehr schwammig, es könnte damit auch Anzahl der Vertauschungen * 2 oder Anzahl der Vertauschungen * 3 gemeint sein, weil für eine Vertauschung zwei Datenwerte ('records') vertauscht werden müssen und der eine dafür eventuell zwischengespeichert werden muß.

Vielen Dank! 

Ja, Google gibt auch keine brauchbaren Ergebnisse für "Recordbewegungen Algorithmus".
Ich weiß nicht, wieso sich meine Hochschule immer eigene Begriffe ausdenken muss. 
Im Skript ist nur angegeben "die Anzahl Recordbewegungen = M(n)."
Für Insertionsort ist
– M(best) = 2*(n-1) ∈ O(n)
– M(worst) = 2*(n-1)+n*(n-1)/2 =n2/2+3/2n-2 ∈ O(n2)

Was eine Recordbewegung IST steht im gesamten Skript nicht.

Danke noch mal!

2

Mit "Record" wird (wurde) ein Datensatz bezeichnet.

Record(Pascal) = struct(C) = Row(Datenbank)

Betrachtet man den zu sortierenden Datenbestand als Array von Records und geht daran, die unmittelbar zu sortieren, müssen innerhalb dieses Bestandes Records vertauscht werden.

Das ist aber etwas, war nur noch jemand macht, der sich die Hose mit der Kneifzange anzieht, man erspart sich die Vertauschungen, indem man nur Referenzen auf die eigentlichen Daten sortiert.

Was möchtest Du wissen?