Buublesort algo

Sandro95

Bekanntes Mitglied
Hey leute , ich verstehe wie der Bubblesort algo vorgeht und was passiert aber bei der Aufgabe komme ich etwas ins grübeln vlt kann mir ja jmd meinen Fehler erklären ich wäre mehr als dankbar:)

hierbei handelt es sich um eine altklausur aufgabe und hierbei handelt es sich um den bubbel sort nur rückwarts , wieso kriege ich das nicht ganz sortiert ?
Der algo läuft doch so , anfangs vergleiche ich das letzte und vorletzte element und gehe paarweise weiter bis j = dem Index 0 ist dann verlasse ich die innere schleife und gehe wieder in die äußere und das gleiche spiel wieder nur das ich jetzt mit dem vorletzten element und dem dritt letzten element anfange zu vergleiche usw
 

Anhänge

  • WhatsApp Image 2020-08-01 at 00.25.28.jpeg
    WhatsApp Image 2020-08-01 at 00.25.28.jpeg
    100,1 KB · Aufrufe: 16

Meniskusschaden

Top Contributor
und gehe paarweise weiter bis j = dem Index 0 ist
Was meinst du hier mit "paarweise weiter gehen"?
Wenn du dir die abgedruckte Implementierung mal genauer anschaust, siehst du, dass innerhalb der inneren Schleife überhaupt keine Vertauschungen vorgenommen werden und innerhalb der äußeren Schleife nur eine Vertauschung pro Durchlauf. Es kann also maximal acht Tauschoperationen geben - deutlich weniger, als du eingetragen hast.
 

Sandro95

Bekanntes Mitglied
@Meniskusschaden doch klar die vertauschung folgt doch in der inneren (der zweiten for schleife ) ?
ich habs noch mal versucht (siehe anhang)

ich dachte eig , dass ich pro durchlauf also erst den index 8 und 7 vergleiche , dann index 7 mit 6 , dann 6 mit 5 .. etc
 

Anhänge

  • WhatsApp Image 2020-08-01 at 01.30.27.jpeg
    WhatsApp Image 2020-08-01 at 01.30.27.jpeg
    111,3 KB · Aufrufe: 14

Meniskusschaden

Top Contributor
doch klar die vertauschung folgt doch in der inneren (der zweiten for schleife ) ?
Nein. Wenn du die innere Schleife mal mit geschweiften Klammern schreiben würdest, würde so etwas heraus kommen:
Java:
for () {
    if () {
        m=j;
    }
}
// Dreieckstausch
So sieht man auch, dass der Dreieckstausch erst nach Abschluss der inneren Schleife vollzogen wird.

Das ist übrigens kein BubbleSort sondern SelectionSort.
 

insert2020

Aktives Mitglied
Das ist ein umgekehrt laufender Selection-Sort. Best Case (n²), Worst Case (n²), Stabil: ja, Tabelle... zu faul. :D (Bzw., mir ist die in der Vorlesung angewandte Schreibweise nicht vertraut)
 

Sandro95

Bekanntes Mitglied
ich danke euch.. dann versuche ich die Tabelle mal mit den Selectionsort aber morgen früh .. bin davon ausgegangen das es sich hierbei um einen Bubblesort handelt.
Könnte ich meine lösung dann morgen hier noch mal reinschickendamit ich drüber schaut ß :)

@insert2020 mir gings viel mehr umaufgabe b :p
 

Sandro95

Bekanntes Mitglied
Aber nehmen wir dür jetzt an , dass es ein bubblesort wäre , wäre dann die Tabelle richtig ?
Selection mache ich sann morgen
 

insert2020

Aktives Mitglied
Habs schnell getestet, Selection-Sort ist bemerkenswerterweise nicht stabil:
Java:
	private static class WrapInt {
		int value;
	}

	public static void sortiere(WrapInt[] feld) {
		for (int i = feld.length - 1; i > 0; i--) {
			int m = i;
			for (int j = i - 1; j >= 0; j--) {
				if (feld[j].value > feld[m].value) {
					m = j;
				}
			}

			WrapInt t = feld[i];
			feld[i] = feld[m];
			feld[m] = t;
		}
	}

	public static void main(String[] args) {
		WrapInt[] f = new WrapInt[5];
		for (int i = 0; i < f.length; i++) {
			f[i] = new WrapInt();
		}
		f[0].value = 3;
		f[1].value = 2;
		f[2].value = 1;
		f[3].value = 2;
		f[4].value = 2;
		HashMap<String, String> map = new HashMap<>();
		for (int i = 0; i < f.length; i++) {
			map.put(f[i].toString(), f[i].value + "@" + i);
		}

		System.out.println(Arrays.stream(f).map(w -> map.get(w.toString())).collect(Collectors.joining(", ")));
		sortiere(f);
		System.out.println(Arrays.stream(f).map(w -> map.get(w.toString())).collect(Collectors.joining(", ")));
	}
Code:
3@0, 2@1, 1@2, 2@3, 2@4
1@2, 2@4, 2@1, 2@3, 3@0
Hier wurde das Element an Platz 4 vor die Elemente an Platz 1 und 3 getauscht, obwohl alle drei Elemente gleich sind.

Aber nehmen wir dür jetzt an , dass es ein bubblesort wäre , wäre dann die Tabelle richtig ?
Ich kenn mich doch mit der Schreibweise nicht aus. ;)
 
K

kneitzel

Gast
Aber den Algorithmus kann man einfach anpassen, damit er stabil ist. Statt der > Abfrage einfach ein >= nutzen. Dann sollte die Reihenfolge von gleichen Elementen nicht mehr verändert werden.

Edit: zu kurz gedacht. Das reicht natürlich als Anpassung nicht, da ja das Element vom Anfang direkt nach hinten genommen wird, wodurch natürlich die Stabilität auch beeinflusst wird ... war zu kurz gedacht.
 
Zuletzt bearbeitet von einem Moderator:

Sandro95

Bekanntes Mitglied
@insedie schteibqeise der Tabelle ist , einfach wie der algo arbeiten würde step by step würde das passen wenn wir annehmen das es sich um ein bubblesort handelt ( ich weiß ist keiner)?
 

Meniskusschaden

Top Contributor
Aber nehmen wir dür jetzt an , dass es ein bubblesort wäre , wäre dann die Tabelle richtig ?
Ich würde sagen, das wäre dann trotzdem noch nicht korrekt. Zum Beispiel die dritte Zeile deiner Tabelle aus #3:
Code:
2   3   4   5 | 8   6   9   7   8  // Dein Ergebnis für Zeile 3
2   3   4 | 5   8   6   9   7   8  // Korrektes Ergebnis für Zeile 3
Nach dem dritten Durchlauf wäre nur für die ersten drei Elemente garantiert, dass sie sich an der richtigen Position befinden. Auch wenn die vierte Position dann schon durch Zufall richtig belegt wäre, könnte der Algorithmus das nicht wissen und würde dennoch die nächste Iteration mit dem vierten Element beginnen.
 

Sandro95

Bekanntes Mitglied
woran erkenne ich bzw kann ich einen bubblesort von einem Selectionsort unterscheiden ? In der Klausur würde ich denken , dasss es sich um einen bubblesort handelt hat wer vlt iein Tipp ?
 
K

kneitzel

Gast
Bubblesort tauscht bei Bedarf direkt in der inneren Schleife. Der größte oder eben kleinste Wert wandert als wie eine Blase nach oben (sinkt nach unten).

Selection Sort selektiert in der inneren Schleife nur ein Element, das dann nach der Schleife getauscht wird.
 

Sandro95

Bekanntes Mitglied
wäre dann meine Tabelle falsch ? Beim selection Sort gehe ich doch wie hier jetzt beim letzten element die schleife durch und tausche das letzte element immer mit einem noch kleineren element
 

Sandro95

Bekanntes Mitglied
also wird beim ersten tausch mit einem größeren Element der Schleifendurchgang beendet und mit dem Vorletzten Element weiter gemacht ?
 
K

kneitzel

Gast
Spiel den Algorithmus doch einfach einmal durch.

Was passiert denn genau? Schreib das einfach einmal auf einem Zettel genau auf.
Dann solltest du direkt sehen, wie es funktioniert mit der 9 ....
 

mihe7

Top Contributor
Also, Du hast ein Array feld mit den Werten {4,8,5,9,6,3,2,8,7}.

Die äußere Schleife beginnt beim letzten Element, d. h. m = i = 8. Die innere Schleife fängt bei dem Element davor an. Für dieses Array wird in der ersten Iteration der äußeren Schleife j also mit 7 initialisiert. Im Rumpf der inneren Schleife wird nun geprüft, ob das Element an Postion j größer als das Element an Position m ist. Falls ein solches Element gefunden wurde, wird m auf j gesetzt, so dass m das bislang größte gefundene Element darstellt (m steht wohl für maximaler Wert). Am Ende der inneren Schleife ist m also der Index des größten Elements, das sich links vom Element an Position i befindet.

Für i = 8 gilt feld[i] == 7. Die 9 ist größer als 7, daher wird nach der inneren Schleife m == 3 gelten. Jetzt wird das Element an Position i mit dem Element an Position m getauscht, folglich ergibt sich nach dem ersten Durchlauf der äußeren Schleife {4,8,5,7,6,3,2,8,9}
 

Sandro95

Bekanntes Mitglied
@JustNobody meine Tabelle die ich eben geschickt habe ist also falsch , richtig ? So wie mir @mihe7 erklärt hat würde beim ersten durchgang die 8 mit der 7 getauscht werden . so beim zweiten durchgang fangen wir fdann doch beim index7 an und kommen doch nicht mehr dran am index 8 wo die 8 drin steht .
Wie soll dann später die 9 dort hinkommen?
 

Sandro95

Bekanntes Mitglied
@mihe7 ja dann müsste aber doch meine Tabelle stimmen ? oder wird NUR das größte Element dann getauscht ? alsi die 9 im Index 7 wird nicht getauscht sondern die 9 im index 4 mit der 7 im index 8 ?
 

Meniskusschaden

Top Contributor
woran erkenne ich bzw kann ich einen bubblesort von einem Selectionsort unterscheiden ?
Diese Sortieralgorithmen haben ja sehr sprechende Namen, die die Algorithmus-Idee gut beschreiben. Man muss sich also nur z.B. per Schreibtischtest ansehen, wie der Algorithmus arbeitet und kann es dann schon ganz gut zuordnen.

Das größte/kleinste Element des unsortierten Bereichs steigt durch Positionstausch mit dem Nachbarn kontinuierlich nach oben bis an die Spitze des unsortierten Bereichs (wenn man sich eine vertikale Anordnung vorstellt).
Verhalten wie eine Luftblase im Wasser => BubbleSort.

Man sucht sich das größte/kleinste Element des unsortierten Bereichs heraus (komplex) und legt es in den sortierten Bereich (trivial).
Hauptarbeit beim Auswählen des Elements => SelectionSort.

Man nimmt sich das nächste Element des unsortierten Bereichs (trivial) und fügt es an der richtigen Stelle im sortierten Bereich ein (komplex).
Hauptarbeit beim Einfügen => InsertionSort.
 

user30

Mitglied
woran erkenne ich bzw kann ich einen bubblesort von einem Selectionsort unterscheiden ?
BS vertauscht direkt,
SS sucht das Maximum oder Minimum und vertauscht dann,
InsertionSort fügt ein und schiebt alle Elemente auf oder erstellt eine neue Kollektion.
Das sind die wesentlichen Unterschiede, von jedem Algorithmus gibt es aber unterschiedliche Varianten in der Umsetzung.
Deswegen ist es gar nicht schlecht, dass euch Code gegeben wird.
Solche Tabellen sind aber immer Horror.
 

Ähnliche Java Themen

Neue Themen


Oben