Buublesort algo

Diskutiere Buublesort algo im Java Basics - Anfänger-Themen Bereich.
S

Sandro95

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

M

Meniskusschaden

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

Meniskusschaden

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

insert2020

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)
 
S

Sandro95

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
 
S

Sandro95

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

insert2020

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. ;)
 
J

JustNobody

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:
S

Sandro95

@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)?
 
M

Meniskusschaden

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

Sandro95

Ah verstehe , also wäre halt nur der Strich an der falschen Stelle da der algo das nicht wissen kann ?
 
S

Sandro95

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 ?
 
J

JustNobody

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

Sandro95

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
 
Thema: 

Buublesort algo

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben