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
5 Antworten
Tipp 1: Du setzt beim dritten Element an. Die Variable i hat den Wert 1, die Inkrementation erhöht auf 2.
Tipp 2: Wenn du den Wert von a[i] nimmst und in a[i - 1] speicherst, haben beide Elemente denselben Wert. Folgend a[i - 1] in a[i] zu schreiben, bringt nicht mehr viel.
Nochmal zur grafischeren Visualisierung:
a[0] = 4
a[1] = 2
swap:
a[0] = a[1] >> a[0] hat nun den Wert 2
a[1] = a[0] >> a[1] ändert sich nicht, ist nach der Zuweisung immer noch 2
Du solltest dir den Wert von a[0] zwischenspeichern, bevor du ihn überschreibst und diese temporäre Variable später a[1] zuweisen.
Der Ablauf deines Programmes (ab der Schleife) sieht bei einer Beispielmenge [-3, -4, -5, -2] derzeit so aus:
i++ >> i = 1
-4 < -3 >> true, neue Reihenfolge ist: [-4, -3, -5, -2]
1 < 3 >> true
i++ >> i = 2
-5 < -3 >> true, neue Reihenfolge ist: [-4, -5, -3, -2]
2 < 3 >> true
i++ >> i = 3
-2 < -3 >> false, Reihenfolge der Elemente bleibt
3 < 3 >> false
Das bedeutet, deine Methode bubbelt nur einen Wert nach hinten, denn es findet nur ein Durchlauf durch die Liste statt. Es sollte aber mehrere Durchläufe geben. So oft, bis alle Elemente an der richtigen Stelle stehen.
Schau dir dazu die Animation von Wikipedia an (auch wenn sie langsam ist). Jeder Durchlauf durch die Menge ermittelt durch paarweise Vergleiche den größten/kleinsten Wert und sortiert ihn an das Ende/den Anfang der Liste. Nach einem Durchlauf verringert man den Mengenbereich, den man sich anschauen möchte (der zuvor gebubbelte Wert am Anfang/Ende der Liste ist ja nun korrekt sortiert) und iteriert über diesen.
Mit jedem Durchlauf wird ein Wert richtig sortiert und der Mengenbereich verkleinert sich, bis man nur noch ein Element übrig hat. Dieses muss zwangsweise an seiner richtigen Stelle stehen.
du brauchst eine temporäre variable zum tauschen ...
a = b
b = a
vertauscht nicht a und b, sondern setzt a und b auf den selben wert den b am anfang hatte, das wolltest du ja nicht ---- also:
temp = a
a = b
b = temp
weiterer tipp. bubblesort geht mit 2 ineinander verschachtelten schleifen (eben 2 verschiedene laufvariablen)
for i = 1 to n-1: for j = i to n.
Du benötigst zwei for-Schleifen und eine if-Abfrage.
ok aber da steht while do schleife geht das auch mit 2 while do schleifen?
Bitte 30 Sekunden nachsitzen und den Kopf einschalten!
Was ist eine FOR-Schleife? Die beginnt bei einem Anfangswert und zählt ab da eigenständig weiter. Sie endet, wenn ein Endwert erreicht ist. Mathematisch endet sie also, wenn der Schleifenwert größer oder gleich dem Endwert ist. Richtig?
Was ist eine WHILE-Schleife? Sie läuft, bis eine Bedingung erreicht ist. Das kann die gleiche Bedingung wie bei der FOR-Schleife sein. Nur den Anfangswert initialisieren und den Schleifenwert erhöhen macht sie nicht automatisch, das muss man also selbst hinzufügen.
Übrigens: Man kann hier auch Quellkode direkt einfügen. Das lässt sich besser lesen und spart Bytes.
Was ist das eigentlich für eine Seite?
Meine Uni Seite wo wir halt Online Aufgaben vom Dozenten zum Üben bekommen haben.
Okay, aber wenn du bei jeder Übungsaufgabe hier fragst, wo bleibt dann der Sinn der Übung?
nicht bei jeder, nur die die ich nicht verstehe, und hab ja extra gesagt keine Lösung tippen nur Tipps geben
Wie sieht denn dein Ansatz aus? Ansonsten wäre mein Tipp, dass du erstmal den Pseudocode von Wikipedia in Java übersetzt.
a1[i-1] = a1[i];
a1[i] = a1[i-1]
Damit willst du wahrscheinlich die beiden Werte vertauschen. Das klappt so allerdings nicht, nach der ersten zitierten Zeile hat a1[i-1] den gleichen Wert wie a1[i]. Und den selben Wert schreibst du dann nochmal in a1[i], am Ende deiner "Vertauschaktion" sind die Werte nicht vertauscht, sondern haben beide den gleichen Wert (das müsste der von a1[i] sein). Da brauchst du eine Zwischenvariable. Irgendwas in Richtung
int temp = a1[i - 1];
a1[i - 1] = a[i];
a[i] = temp;
Ansonsten gilt das, was milos2 schreibt (und was auch bei Wikipedia steht) - du brauchst zwei verschachtelte Schleifen.
ok danke hab deine beiden tipps befolgt es klappt fast ja kannst du nochmal drüber schauen ich hab beide werte zur Sicherheit in einer eigenen Variable zwischengespeichert die unteren 2 Fälle mit minus zahlen klappen nicht ich weiß nicht wieso
https://ibb.co/LJfyVVG