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!

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Dunkelalb

16.07.2016, 14:51

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

BillHatayu

Fragesteller

16.07.2016, 15:01

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!

Mikkey

16.07.2016, 15:51

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.

Ähnliche Fragen

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Welchen Algorithmus verwende ich, um 50 Zahlen mit möglichst wenig Vergleichen und Vertauschungen zu sortieren?

Die Aufgabe ist, einen beliebigen Sortieralgorithmus aus berliebiger Quelle in Java zu implementieren, um bis zu 50 Zahlen zu vergleichen. Gewertet wird nur die möglichst geringe Anzahl an Vergleichen und Vertauschungen. Der Rest ist egal. Keine Zahl kommt Zweimal vor. Welcher Algorithmus eignet sich da am besten?

...zur Frage

PHP verschiedene Arrays vergleichen?

Hey,

ich habe ein Problem und zwar muss ich zwei Array vergleichen. Ein Beispiel Array von mir:

Array
(
    [0] => 15
    [1] => 85
    [2] => 53
    [3] => 12
    [4] => 6
)

Von diesem Array habe ich zwei. In den beiden stehen hauptsächlich verschiedene Werte. Doch ich muss nun überprüfen, ob in dem einem Array ein Wert drin steht vom anderem. Die Array können auch unterschiedlich lang sein. Daher muss ich also irgendwie jeden Wert in dem einem Array mit jedem Wert aus dem anderen vergleichen und gucken ob sie gleich oder unterschiedlich sind.

Am besten wäre es auch noch wenn sobald einer gleich ist das "true" einfach zurück gegeben wird.

Ich hoffe ihr habt eine Idee und könnt mir damit weiterhelfen.

Danke im Voraus

...zur Frage

Java Programm auf gleiche Zahlen prüfen?

Wir müssen für die Schule ein Beispiel losen:

Es werden 2 Array angelegt beide mit den Zahlen von 1-9. Das Programm soll prüfen ob jede Zahl von einem Array in dem anderen auch vorhanden ist die Reihenfolge und Anzahl ist egal.

zB: falsch: Array1:1,2,8,8

Array2:1,4,8,2

zB: richtig: Array1:1,2,8,4,0

Array2:1,2,2,8,0,4,0

Meine Frage ist wie mache ich dass?

Kann mir bitte jemand helfen?

...zur Frage

Java String vergleichen mit Array /Liste?

Hallo zusammen :)

Ich schreibe in Java. Kann man denn in Java einen String (welcher aus mehreren Sätzen besteht) vergleichen mit einem Array ? Als Beispiel:

If(Content.contains(//hier der array))

Ist das irgendwie möglich ? Wenn nicht, gibt es da andere Lösungen?

MFG

...zur Frage

Ist ein Bild (digital jpg zum Beispiel) nichts anderes als ein 2d Array von Pixeln?

?? Also Farbquadraten

wenn ich also 2 Bilder auf Gleichheit vergleichen will gehe ich einfach jedes Pixel durch oder ? Und vergleiche den Farbcode

...zur Frage

"bestanden" und "nicht bestanden" zählen - Excel?

Hallo,

folgendes Beispiel (nur Theorie): Es gibt eine bestimmte Anzahl an Teilnehmern bei einem Test. Eine gewisse Anzahl hat "bestanden" und eine gewisse Anzahl eben nicht (="nicht bestanden").

Wie kann man mittels einer Funktion auf Excel berechnen, wie viele (=Anzahl) bestanden bzw. nicht bestanden haben. Also NICHT einfach im Kopf ausrechnen (wäre ja einfach), sondern mittels einer Funktion!

Hier ein Screenshot:

Vielen Dank an jene, die mir vielleicht helfen können!

(Die HA bekommt natürlich einen Stern!)

...zur Frage

Java Algorithmus zum herausfinden der längsten kette von Zahlen?

Wie der Titel bereits aussagt soll ein Algorithmus entwickelt werden der am Ende die Anzahl der elemente der längsten kette von sich wiederholenden Zahlen ausgibt also beispiel: 1 1 1 1 2 2 2 2 2 1 2 4 4 4 4 4 4 4 4 4 soll 9 ausgeben da die reihe der vieren nach der 2 die längste kette ist mein Programm bis jetzt sieht wie folgt aus

meine Frage ist jetzt wo liegt hier mein Fehler?

...zur Frage

Anzahl eines arrays in c++ ermitteln?

Ich bin noch ein Anfänger in Sachen Programmierung. Ich habe einen Array

Getraenk[5]. Jetzt möchte ich herausfinden wie ich die Anzahl ausgeben kann sprich am Ende soll bei der cout Ausgaben eine 5 stehen weil ja 5 Elemente drin sind. Jetzt sitze ich schon einige Zeit hier aber habe keine ahnung wie das geht. Könnt ihr mir helfen, vielleicht sogar mit Code als Beispiel? Bin noch ein Anfänger also bitte so einfach wie möglich

...zur Frage

C++ durchschnittsberechnung array wie?

Guten Tag,

ich möchte gerne eine Durchschnittsberechnung durchführen. Dazu habe ich zwei Arrays gegeben:

String Stadt[100]

Int anzahl[100]

In der Aufgabe geht es darum die Anzahl alles Bahnhöfe in der jeweiligen Stadt zu zählen(Anzahl = Anzahl der Bahnhöfe in der Stadt). Nun will ich die Anzahl aller Werte im Int anzahl[100] zusammenzählen und durch die Anzahl aller Städte teilen. Die Stadt ist aber ein String wert weshalb man das nicht so leicht teilen kann. Bei zwei Punkten brauche ich also hilfe:

1. Wie rechne ich alle Städte zusammen?

2. Wie Teile ich die Summe der Städte durch die gesamte Anzahl?

Ich hoffe ich könnt mir helfen

...zur Frage

Finde die zwei kleinsten Elemente mit 1,5n - 2 Vergleichen?

Hallo allerseits,

heute habe ich in meiner Berufsschule die Aufgabe bekommen, in einem Array / Liste die zwei kleinsten Zahlen zu finden mit maximal 1,5n - 2 Vergleichen.
Mein erster Gedanke war, ein Sortieralgorithmus drüber laufen zu lassen und dann einfach die ersten beiden Elemente zu returnen. Das Problem ist, dass mir kein Algorithmus mit nur 1,5n -2 Vergleichen einfällt und ich keine andere effiziente Lösung finde.

Hat jemand eventuell eine gute Lösung? Gerne iterativ und rekursiv.

Danke!

...zur Frage

Zählen von Wörtern in einer Zeichenkette?

Wieso kommt die Falschw Anzahl von dem gesuchtem Wort heraus, wenn ich das Programm ausführe und wie repariere ich das?

Als Beispiel kommt wenn ich als Satz eingebe: du und ich und die welt

Und nach dem Wort 'und' suche 8mal heraus.

...zur Frage

Ich soll einen Array erstellen der 20 Zeilen und 10 Spaltan hat, ist das so korrekt?

Ich soll nach Anzahl der kästchen den Array bilden, ich habe ja offensichtlich 20 Zeilen und 10 SPalten! (Was man halt sehen kann, mann muss diese Vierecke als 1 zählen!)

Unser Prof hat den Array so ersellt:

Ich glaube jedoch, dass das falsch ist oder? Weil wir haben ja nicht 10 zeilen und jeweils 20 spalten, sondern 20 zeilen und jeweils 10 spalten?

Wäre dementsprechend nicht shape[20][10] richtig?

...zur Frage

Anzahl aller gefüllten Arrays aufzählen in Java?

Wie lautet die Syntax zur Aufzählung der gefüllten Arrays in Java?

Beispiel:

int[ ] array = new int[4];

array[0] = 3;

Die restlichen bleiben leer und man möchte auf die Konsole, die Anzahl der gefüllten Arrays, anzeigen. (Nur die Anzahl nicht den Wert!)

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen