Frage von BillHatayu, 37

Sortier-Algorithmus, Insertionsort - Was ist eine Recordbewegung?

Bei einem Sortier-Algorithmus (zum Beispiel Insertionsort)kann man für einen gegebenen Array die Anzahl an Vergleichen zählen, aber eben auch die Anzahl an Recordbewegungen.

Was ist ein Recordbewegung?

Danke!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von Dunkelalb, 28

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ß.

Kommentar von BillHatayu ,

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!

Antwort
von Mikkey, 20

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.

Keine passende Antwort gefunden?

Fragen Sie die Community