ist mein insertionSort verständnis richtig?

{8,7,2,6,1,0,5,7,7}

wenn ich folgendes array habe, dann wurde gesagt, dass die 8 bereits beim ersten durchlauf an die richtige stelle gesetzt wird also:

7 2 6 1 0 5 7 7 8

aber müsste das nicht

7 8 2 6 1 0 5 7 7

lauten?

also dann diese abfolge:

Bild zum Beitrag

1 Antwort

Schachpapa

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

rechnen, Funktion, Gleichungen

08.07.2023, 22:05

dann wurde gesagt, dass die 8 bereits beim ersten durchlauf an die richtige stelle gesetzt wird

Wurde das so gesagt? Mit dem Beispiel? Beim InsertionSort hast du immer einen sortierten und einen unsortierten Teil.

Am Anfang steht die 8 im sortierten Teil, ein einziges Element ist immer korrekt sortiert.

Mit jedem Einfügeschritt wandert die 8 eine Position weiter, ist also im sortierten Teil an der richtigen Stelle. Aber erst ganz am Schluss, wenn es keinen unsortierten Teil mehr gibt, ist sie endgültig an der richtigen Stelle.

So wie in der unteren Abfolge.

Woher ich das weiß:Berufserfahrung

IfElseIf

Fragesteller

08.07.2023, 22:13

Ja genau der untere Teil ist das was mein Code immer produziert, ja etwas ineffizient weil ich immer runter zu 0 gehe aber es funktioniert, jemand meinte nämlich dass insertion dort bedeutet dass bei der 2. Zeile die 8 bereits ganz rechts sein sollte

Schachpapa

08.07.2023, 22:32

@IfElseIf

evtldocha gibt normalerweise gute Antworten, aber die ist falsch.

IfElseIf

Fragesteller

09.07.2023, 00:24

@Schachpapa

Ok Danke

Hey Leute, ich hab folgendes Problem...

Ich speichere Scores als Array (username, score) in einem anderen Array, in dem alle Scores mit Namen vorhanden sind.

In meiner Scoreliste möchte ich nun alle Scores sortiert anzeigen. Ich kann die Daten sowohl in PHP, als auch in Javascript sortieren. Kann mir jemanden einen Code geben für eine der beiden Sprachen?

JSON zum Verständnis:

[["max", 1] , ["moritz",2]]

...zur Frage

Java in Array an bestimmter Stelle einfügen

Hallo, habe ein kleines Problem beim einfügen eines Strings in ein String Array in Java. Ich muss nach Wichtigkeit einen String in ein Array einfügen. Muss den String an einer bestimmten Stelle im Array einfügen. Jetzt das Problem: Wenn ich etwas an der 5ten Stelle einfügen möchte und die 5te Stelle bereits vergeben ist wird der String, der bereits an der Stelle ist, überschrieben. Möchte aber das sich alles um eine Stelle nach hinten verschiebt. Danke schon mal im Voraus

...zur Frage

Wie schaut man in C ob eine Zahl bereits vorhanden ist?

sagen wir ich habe ein array a[ ] = {9,1,5,6,5,9};

jetzt will ich ne funktion schreiben die schaut ob und wenn ja wie oft eine zahl mehrfach vorhanden ist. also hier die 9 2mal und die 5 zweil mal

dafür müsste ich ja das array durchgehen und die i-te zahl mit jeder andere vergleichen, also ab dieser zahl und nicht von vorne.

also bei der 1. 9 mit 1,5,6,5,9 vergleichen

bei der 1 mit 5 6 5 9

bei der 5 mit 6 5 9

und bei der 6 5 9

usw.

wie würde ich da ne funktion schreiben?

...zur Frage

Programmieren Python?

Hallo,

was ist bei diesem Programm bei Python falsch? Ich wollte nämlich testen, ob man mit der Formel für Pythagoreische Tripel (a = m² – n² ; b = 2mn ; c = m² + n²) jede beliebige Zahl für m und n einsetzen kann und dann automatisch ein pythagoreisches Tripel erhält (unter der Bedingung: m>n) …

...zur Frage

Java wo liegt der Fehler?

Hallo gutefrage-Community,

ich habe unten gezeigten Quellcode verfasst und dabei keinerlei Fehlermeldungen oder Exceptions erhalten. Am Ende kommt aber irgendwie trotzdem nicht heraus, was herauskommen soll.

Was ich erwarte:

Aus einem JTextField erhält man einen String "input" wie z.B. 2x+5=10x-3. Dieser wird zuerst beim "=" gesplittet. Daraus erhält man ein Array mit zwei Strings: 2x+5 und 10x-3. Diese beiden Arrays sollen nun an allen "+" und "-" gesplittet werden. Deshalb wird eine Schleife zweimal durchlaufen und dabei im ersten Durchlauf der erste und im zweiten Durchlauf der zweite String verarbeitet. Danach wird bei jeder Zahl mit "x" das "x" entfernt und ein boolean auf true gesetzt. Was am Ende herauskommen soll:

Drei Arrays (int num[], boolean isFactorOfVar[] und boolean isOnRightSide[]), die immer dem gleichen Index entsprechen, also: num[0] gehört zu isFactorOfVar[0] und zu isOnRightSide[0], num[1] gehört zu isFactorOfVar[1] und zu isOnRightSide[1] usw. Dabei soll num[] der Zahl entsprechen, isFactorOfVar, ob ein x am Ende entfernt wurde und isOnRightSide[], ob sich diese Zahl auf der rechten Seite des "=" befindet. Hier ist das am Anfangsbeispiel 2x+5=10x-3 gezeigt:

num[0] = 2; isFactorOfVar[0] = true; isOnRightSide[0] = true
num[1] = 5; isFactorOfVar[1] = false; isOnRightSide[1] = true
num[2] = 10; isFactorOfVar[2] = true; isOnRightSide[2] = false
num[3] = 3; isFactorOfVar[3] = false; isOnRightSide[3] = false

Was herauskommt:

num[0] = 2; isFactorOfVar[0] = true; isOnRightSide[0] = nicht angezeigt
Fehlermeldung

Mein Code:

Fehlermeldung:

...zur Frage

Periodizität einer Folge?

Ist die Folge aus a²+a mit a Element N modulo p für jedes p irgendwann periodisch?

...zur Frage

Verständnisproblem lim sup, lim inf?

Hallo liebe Community. Ich habe ein paar Probleme, dieses Thema völlig zu durchsteigen. Was mir derzeit Probleme bereitet:

lim sup soll ja der größte Häufungspunkt sein. lim inf der Kleinste. Aber was, wenn ich nur einen Häufungspunkt habe, betrachten wir die Folge:

Also eine alternierende Folge, die nach oben nicht konvergiert, nach unten aber schon, gegen 0. Wäre dann lim sup = lim inf = 0? Weil ja 0 dann der größte Häufungspunkt wäre, aber gleichzeitig ist a_n ja nicht nach oben beschränkt, also müsste ja lim sup = +inf gelten. Was ist nun richtig?

...zur Frage

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

Was muss ich anwenden, um das Project Euler Problem 715 zu lösen?

Ich benötige Hilfe bei der Lösung des Project Euler Problems 715, welches sich mit einem höchst komplexen kombinatorischen Problem mit diophantischen Gleichungen beschäftigt. Ich versuche, die Anzahl von 6-Tupeln (x1, x2, x3, x4, x5, x6) zu bestimmen, für die gilt:

Alle xi sind ganze Zahlen mit 0 < xi < n.
ggT(x1^2 + x2^2 + x3^2 + x4^2 + x5^2 + x6^2, n^2) = 1

Gesucht ist g(10^12) mod 1000000007.

Um das Problem anzugehen, habe ich versucht, den Lösungsraum mithilfe von zahlentheoretischen und kombinatorischen Methoden einzugrenzen. Mein aktueller Ansatz ist es, die diophantische Gleichung x1^2 + x2^2 + x3^2 + x4^2 + x5^2 + x6^2 = k * n^2 + 1 darzustellen, wobei k eine ganze Zahl ist.

Ich habe versucht, die Anzahl der Lösungen für jedes k mithilfe des Sternschen Dreiecks der Pfeilschen Dreieckszahlen zu berechnen, indem ich die Anzahl der Wege im Dreieck zähle, die zu einem k-fachen von n^2 + 1 führen. Danach wollte ich die Anzahl der Lösungen für jedes k modulo 1000000007 addieren.

Leider führt dieser Ansatz zu inkorrekten Ergebnissen. Welche mathematischen Konzepte oder Techniken könnte ich anwenden, um das Problem auf eine effiziente und korrekte Weise zu lösen?

Jede Hilfe ist willkommen, insbesondere solche, die auf zahlentheoretischen oder kombinatorischen Methoden basieren.

...zur Frage

A Teilmenge von B impliziert Komplement von B ist Teilmenge von Komplement von A?

Hey, stimmt die Implikationen oben? Wenn ja, dann bräuchte ich die für einen Beweis, also wäre super, wenn ihr mir sagen könntet, wieso die Implikationen stimmt oder woraus ihr das ableitet.

Dankeeeeeeee:D

...zur Frage

Java Bubble Sort Algorithmus programmieren wer kann mir helfen (bitte keine Lösung schreiben sondern nur Tipps geben)?

Die Aufgabenstellung lautet:

"Damit Sie sehen wie nervig das Sortieren eines Arrays wirklich sein kann wenn man es selbst programmieren muss: implementieren Sie einen einfachen Sortieralgorithmus in einer Methode namens 'bubblesort'. Diese Methode erwartet einen Parameter 'x' wie in der letzten Aufgabe, und verfährt auch genauso mit ihm. Die Sortierung wird wie folgt durchgeführt: angefangen beim zweiten Array-Element (also mit Index 1) prüfen Sie für alle Elemente, ob sie kleiner sind als ihr Vorgänger, und vertauschen sie sofort falls ja. Dies wird so lange durchgeführt, bis bei einem kompletten Durchlauf durch das Array (beginnend bei Index 1) keine Vertauschung mehr vorgenommen werden muss, in diesem Fall ist das Array sortiert. Falls das Array 0 oder 1 Elemente hat muss nichts getan werden da solche Arrays bereits sortiert sind (warum?). Tipp: die perfekte Gelegenheit eine do/while-Schleife zu benutzen!"

Mit freundlichen Grüßen

...zur Frage

Ergebnismenge beim Würfel?

Hey Leute ich habe eine Frage zur Ergebnismenge eines Tetraeder Würfel.

Wenn dieser 1 einmal geworfen wird ist es doch Omega {1,2,3,4}

Jetzt meine Frage wie Liste ich die Menge auf bei einem 2 maligen Wurf. Muss ich quasi alle möglichen "Pärchen bilden" also zb: Omega {(1,1),(1,2),...(4,4)}. Oder muss ich nur die Zahlen die kommen könnten doppelt auflisten also {1,1,2,2...,4,4}?

...zur Frage

Konvergenz und Grenzwert nachweisen?

Berechnen Sie im Falle der Konvergenz den Grenzwert oder begründen Sie, weshalb der jeweilige Grenzwert nicht existiert.

Brauch mal Hilfe bei der Aufgabe. Doof gefragt wenn x gegen 0 geht, ist der GW nicht dann auch 0?

...zur Frage

Wie soll ich die Monotonie dieser Folge beweisen?

Die folge lautet. 1+ (-1)^n / n

Diese folge steigt mal und dann fällt sie wieder usw.

Wie soll ich die Monotonie dieser Folge beweisen mit der Differenz. an+1 - an > /<0

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen