BubbleSort (Sortieralgorithmus)

[Mr.Pink!]

Guten Morgen liebe Community,

ich setze mich momentan mit dem BubbleSort auseinander, genauer genommen mit der absteigenden Sortierung eines Arrays.
Hier ein Beispiel:

public class zusort {
public static int [] bubblesort_absteigend (int tab []) {
// Bubblesort absteigend
int hilf;
for (int i = 0; i < tab.length-1; i++) {
for (int stelle = 0; stelle < tab.length-1-i; stelle++) {
// kleiner als = absteigend sortieren
if (tab[stelle] < tab[stelle+1]) {
hilf = tab[stelle];
tab[stelle] = tab[stelle+1];
tab[stelle+1] = hilf;
}
}
}
return tab;
}
public static void main(String[] args) {
int [] sor = {34, 23, 0, 0, 123, 567, 3, 43};
// Unsortierte Tabelle in die Methode schicken
bubblesort_absteigend(sor);
// Sortierte Tabelle ausgeben
for (int i = 0; i < sor.length; i++) {
System.out.printf("%4d", sor[i]);
}
}
}

Mein Problem: ich kann die Logik irgendwie nicht nachvollziehen, besonders hapert es bei mir im Vertständnis der doppelten Schleife (Zeile 5/6)...

Ich würde mich freuen, wenn ihr mir dabei helfen könntet.

Danke und lG

 

[XHelp]

Die Umsetzung ist auch etwas unschön.
Bubblesort ? Wikipedia hast du schon gelesen?

 

[Mr.Pink!]

Aha,
also der Pseudocode ist für mich schonmal wesentlich leichter zu verstehen;-)
Hier ist nur eine Schleife vorhanden, die bis zur Länge des Arrays durchzählt und gleichzeitig ein boolescher Wert, der anzeigt, ob zwei nebeneinanderstehende Stellen im Array nun vertauscht wurden oder nicht, sehe ich das so richtig?

Warum wird eigentlich die Länge des Arrays -1 genommen?

Danke und lG




Mr.Pink!

 

[XHelp]

Nein, da sind auch 2 Schleifen vorhanden.

-1 wird genommen, weil du in Zeile 8 oder 10 +1 rechnest und sonst über die Arraybegrenzung hinaus gehen würdest.

 

[Mr.Pink!]

Stimmt, der boolesche Wert steht ja auch nochmal in einer Schleife.

Habe jetzt versucht den Wikipseudocode mal in Java zu realisieren:

public class Nr2 {
	public static void main(String[] args) {
		int [] sor = {34, 23, 0, 0, 123, 567, 3, 43};
		
		bubble(sor);
		
		System.out.println (sor);
	}
	public static int [] bubble (int [] sor) {
		boolean unsortiert;
		int temp;
		
		while (unsortiert = false) {
			for (int i = 0; i < sor.length-1; i++) {
				if (sor[i] < sor[i+1]) {
					temp = sor [i+1];
					sor[i+1] = sor [i];
					unsortiert = true;
				}
			}	
		}
	return sor;
	}
}

Leider bekomme ich als Ausgabe nicht das sortierte Array, sondern das hier:
[I@3e25a5

Könnt ihr mir bitte sagen, was ich da falsch gemacht/übersehen habe?

Danke und lG




Mr.Pink!

 

[AmunRa]

In JAva kann man kein Array direkt über System.out.println ausgeben.

mach am einfachsten eine Schleife und gib dir jedes Element aus

 

[Mr.Pink!]

So,
habe nunmal versucht den Wiki-Pseudocode in Eclipse umzusetzen:

public class Nr2 {
	public static void main(String[] args) {
		int [] sor = {34, 23, 0, 0, 123, 567, 3, 43};
		
		bubble(sor);
		
		System.out.println (sor);
	}
	public static int [] bubble (int [] sor) {
		boolean unsortiert;
		int temp;
		
		while (unsortiert = false) {
			for (int i = 0; i < sor.length-1; i++) {
				if (sor[i] < sor[i+1]) {
					temp = sor [i+1];
					sor[i+1] = sor [i];
					unsortiert = true;
				}
			}	
		}
	return sor;
	}
}

Allerdings erscheint bei mir als Ausgabe nicht das sortierte Array, sondern folgendes:

[I@19821f

Könnt ihr mir sagen, wo der Fehler liegt bzw. was ich übersehen habe?

Danke und lG




Mr.Pink!

 

[Mr.Pink!]

Ich bitte um Entschuldigung für den Doppelpost, aber mein Rechner ist zwischenzeitig abgestürzt.
Ich würde einen netten Mod bitten, den zweiten Post zu löschen.

Danke!

 

[AmunRa]

hast du meinen Beitrag oben gesehen?

 

[jgh]

evtl. ist dieser Beitrag auch obsolet...aber als Verständishilfe für deinen ersten Post, wann welche Schleife abgearbeitet wird:
das ist der Code aus diesem Post erweitert um ein paar Ausgaben.

public static int[] bubblesort_absteigend(int tab[]) {
		// Bubblesort absteigend
		int hilf;
		System.out
				.println("=========================Beginn Äußere Schleife wird "
						+ (tab.length - 1)
						+ "x durchlaufen"
						+ " =========================");
		for (int i = 0; i < tab.length - 1; i++) {
			System.out.println("-Äußere Schleife- Zählvariable i=" + i + " => "
					+ (i + 1) + ". Durchlauf.");
			System.out
					.println("\t\t----------------------Beginn Innere Schleife wird "
							+ (tab.length - i - 1)
							+ "x durchlaufen----------------------");
			for (int stelle = 0; stelle < tab.length - 1 - i; stelle++) {
				if (tab[stelle] < tab[stelle + 1]) {
					System.out.println("\t\t\t\tHier ist also die "
							+ (stelle + 1) + ". Stelle kleiner als die "
							+ (stelle + 2) + ". Stelle, denn " + tab[stelle]
							+ "<" + tab[stelle + 1]);
					hilf = tab[stelle];
					tab[stelle] = tab[stelle + 1];
					tab[stelle + 1] = hilf;
					System.out
							.println("\t\t\tJetzt hast du die beiden Stellen getauscht!");
				} else {
					System.out
							.println("\t\t\tHier ist die größere Stelle an der richtigen Stelle, denn"
									+ tab[stelle] + ">" + tab[stelle + 1]);
				}
				System.out.print("\n\t\t\tAktuelle Reihenfolge:");
				for (int j = 0; j < tab.length; j++) {
					System.out.print(tab[j] + " ");
				}
				System.out.println("\t\tDas war der " + (stelle + 1)
						+ ". Durchlauf der inneren Schleife");
			}
			System.out
					.println("\t\t----------------------Ende Innere Schleife----------------------");
		}
		System.out
				.println("=========================Ende Äußere Schleife=========================");
		return tab;
	}

 

[Mr.Pink!]

Hey Jungs,

vielen Dank für eure Antworten, ich habe Sie alle gelesen und mir zu Herzen genommen.

Hier nun meine fertige Version:

public class Nr2 {
	public static void main(String[] args) {
		int [] sor = {34, 23, 0, 0, 123, 567, 3, 43}; // Deklarierung und Initialisierung des Arrays über Initialisierungsliste
		
		bubble(sor); // Übergabe des Arrays "sor" an die Methode sor
		
		for (int i=0; i < sor.length; i++) { // Ausgabe der einzelnen Arrayelemente mittels for-Schleife
			System.out.println (sor[i]);
		}	
	}
	public static int [] bubble (int [] sor) { // Methode Bubble, die die Arrayelemente absteigend sortieren soll
		boolean unsortiert = true; // Initialisierung boolescher Ausdruck
		int temp; 			
		
		while (unsortiert) { // solange unsortiert = true
			unsortiert = false; // setze unsortier = falsch
				for (int i = 0; i < sor.length-1; i++) { // Durchlaufen der einzelnen Arraystellen mittels for-Schleife
					if (sor[i] < sor[i+1]) { // Wenn Stelle i kleiner als Stelle i + 1,
						temp = sor [i];		//... bekommt temp den Wert an Stelle i
						sor[i] = sor [i+1]; // Wert an Stelle i + 1 wird Stelle i zugewiesen
						sor [i+1] = temp;	// Stelle i+1 wird Wert von temp zugewiesen
						unsortiert = true; // unsortiert wird wieder auf wahr gesetzt
					}
				}	
		}
	return sor; // Rückgabe des sortierten Arrays zur Main-Methode
	}
}

Ich habe allerdings noch zwei Fragen:
1. Wie ist Zeile 15 zu verstehen?
2. Was ist unter "%4d" in einer prinf-Ausgabe zu verstehen?

Wenn ich diese Antworten noch bekommen wäre, wäre das ganze schon "erledigt".

Vielen Dank.

lG




Mr.Pink!

 

[Andi_CH]

1. Wie ist Zeile 15 zu verstehen?

Hm mal auf deutsch übersetzten:
while unsortiert == so lange unsortiert ist

.... und genau das macht die Schleife. Alles wiederholen solange unsortiert ist.
Schau nach was "unsortiert" im Code ist und wo da der Wert verändert wird.

2. Was ist unter "%4d" in einer prinf-Ausgabe zu verstehen?

Die Antwort findest du hier

 

[AmunRa]

while (unsortiert) heißt übersetzt while(unsortiert==true)

was eine while schleife ist wirst du wohl wissen.

unsortiert wird in jedem scheifen durchlauf auf false gesetzt. wenn der Algorithmus eine Vertauschung vornimmt sagt er, dass diese liste nicht sortiert ist. und setzt daher diese Variable wieder auf true und die Liste wird wieder durchlaufen und geschaut ob eine Vertauschung durchgeführt werden muss

 

[AlfAtor]

Zufälligerweise gabs das Thema BubbleSort auch gestern hier. Empfehle ich dir mal durchzulesen.

 

[Mr.Pink!]

while (unsortiert) heißt übersetzt while(unsortiert==true)

was eine while schleife ist wirst du wohl wissen.

unsortiert wird in jedem scheifen durchlauf auf false gesetzt. wenn der Algorithmus eine Vertauschung vornimmt sagt er, dass diese liste nicht sortiert ist. und setzt daher diese Variable wieder auf true und die Liste wird wieder durchlaufen und geschaut ob eine Vertauschung durchgeführt werden muss

Verstehe dann nur nicht ganz warum ich den booleschen Ausdruck nicht einfach nur deklarieren kann und in der While-Schleife erst initialisieren, also folgendermaßen

boolean unsortiert;
while (unsortiert == true) {

Über eine Antwort würde ich mich freuen.

Vielen Dank Kollegen.

lG




Mr.Pink!

 

[jgh]

^^

 

[AmunRa]

while (unsortiert == true) {

das ist keine Initialisierung, sondern ein Vergleich.

D.h. es hat die selbe funktion wie;

int r= 5;
while(r==5){

In unserem Fall muss zuerst

boolean unsortiert = true; //Die variable wird definiert und mit dem Wert true initialisiert

wenn wir die Variable nicht mit true initialisieren würden, bekämen wir einen Kompilerfehler


Edit:

eine while-Schleife hat immer die Form

while(boolscher Wert){ //code der ausgeführt wird  }

mögliche While-Schleifen

while(true){} //Das ist eine Endlosschleife die nie abgebrochen wird.
while(false){}//Der Code der in den geschwungenen Klammern steht wird niemals ausgeführt
boolean run  = true;
while(run){} //Bedeutet dass die Schleife solange ausgeführt wird solange run den Wert true hat
run = false;
while(!run){} //Die Schleife wird solange ausgeführt solange run false ist
int i=5;
boolean b= (i==5)
while(b){} //solange b true ist
while(i==5){} //solange i den Wert 5 hat

 

[Mr.Pink!]

Hi,

also geht man bei booleschen Werten in Bedingungen und Schleifen immer vom "True"-Wert aus, egal welchen Wert boolean vorher hatte?

boolean gefunden = false;
		int stelle = 0;
		
		while (!gefunden & stelle < liste.length) { // Arrayiteration

Die Schleife wird hier nämlich nur ausgeführt, wenn ich das Ausrufezeichen vor den booleschen Wert setze, sonst nicht. Logischerweise müsste er dies aber tun, weil gefunden wäre ja false...

Das ganze verwirrt mich irgendwie total, kann mir da nochmal bitte einer helfen?

Danke und lG




Mr.Pink!

 

[AmunRa]

Wie ich schon geschreiben habe, Der Bereich der in den {}Klammern nach dem while steht wird nur ausgeführ wenn die SChleifenbedingung in den ()Klammern den wert true hat.

wenn du also wie in diesem Beispiel eine boolsche Variable hast, die angibt ob etwas gefunden wurde und die schleife solange laufen soll wie dieser Wert noch nicht gefunden wurde musst du

while(!gefunden){...} schreiben. was soviel hiest wie: solange (noch nicht gefunden){mach}

 

[AmunRa]

Hier noch ein kleiner Link zum lesen

Galileo Computing :: Java ist auch eine Insel – 2.7 Schleifen

 

[SlaterB]

was exakt verwirrt dich, beschreibe es Worten und/oder beziehe dich auf nachvollziehbare Beispiele,
deins mit "while (!gefunden & stelle < liste.length)" ist viel zu kompliziert wenn es dir allein um die Negation geht,

AmunRa hat im Vorposting doch so viele deutliche Beispiele mit Erklärung geschrieben

run = false;
while(!run){} //Die Schleife wird solange ausgeführt solange run false ist

+ davor noch andere Erklärungen wann eine Schleife überhaupt läuft (bei true oder false),
was kann man dazu wirklich noch mehr sagen, was ist unverständlich?

 

[Mr.Pink!]

Wie ich schon geschreiben habe, Der Bereich der in den {}Klammern nach dem while steht wird nur ausgeführ wenn die SChleifenbedingung in den ()Klammern den wert true hat.

wenn du also wie in diesem Beispiel eine boolsche Variable hast, die angibt ob etwas gefunden wurde und die schleife solange laufen soll wie dieser Wert noch nicht gefunden wurde musst du

while(!gefunden){...} schreiben. was soviel hiest wie: solange (noch nicht gefunden){mach}

Sorry, ich glaube wir missverstehen uns gerade ein bisschen.
Das ist mir alles klar, was du schreibst, nur verstehe ich die Logik hinter dieser booleschen Variable nicht, denn wenn ich in die Startbedingung gefunden = false schreibe, wird die Schleife NICHT mehr ausgeführt (heißt aber letztlich nichts anderes als !gefunden):bahnhof:

Kannst du mir das bitte mal erklären?

Danke und lG

 

[AmunRa]

Das

!

ist der NOT Operator in Java. Dieser hat die Aufgabe einen Wert der true ist wird false und ein Wert der false ist wird true.
d.H

!false

ist das selbe wie

true

d.h im Konkreten, deine variable wird mit false initialisiert.

die Bedingung lautet aber

 while(!gefunden)

. Daher wird die schleife ausgeführt, da ja !gefunden ==true ist.


Für mal das aus und schau dir die Ausgabe an

boolean var = true;
System.out.println("var: " +var);
System.out.println("!var: "+ (!var));
var = false;
System.out.println("var: " +var);
System.out.println("!var: "+ (!var));

 

[Mr.Pink!]

Hey,

danke für das Beispiel, ist glasklar und logisch.

Nur, wenn wir wieder hierzukommen, wird es (für mich) unlogisch:

run = false;
while(!run){} //Die Schleife wird solange ausgeführt solange run false ist

Wir legen doch hier fest, dass die boolesche Variable false ist, setzen aber als Startbedingung für die While-Schleife, dass run nicht false ist, sondern true sein muss. Die Sache ist aber die, dass run aus unserer Festlegung heraus eben FALSE ist und die Schleife demnach nicht ausgeführt werden dürfte, wird sie aber trotzdem, nur warum?

Ich bitte um Hilfe, meine (logisch erscheinende) Java-Welt ist am Zusammenbrechen;-)

Danke und lG

 

[AmunRa]

Nein das liest du falsch. while wird immer nur ausgeführt, wenn die Bedingung in den ()Klammern true ergibt also

wenn du die Bedingung die du in den ()Klammern in ein System.out.println schreiben würdest, und dort dann true steht werden die Befehle ausgeführt die in den {}Klammern stehen.

boolean run = false;
while(!run){} //Die Schleife wird solange ausgeführt solange run false ist

in diesem Beispiel legen wir eine boolsche Variable run an un geben dieser den wert false.

Als nächstes kommen wir zu einer Schleife. Hier gibt es bei einer while Schleife immer zwei möglichkeiten. Erste Möglichkeit
die Variable run hat den Wert true dann wird nun der Ausdruck in den runden Klammern ausgewertet. !run -> !true -> false
da der ausdruck false ergibt wird der Schleifenkörper nicht Ausgeführt.


Dieser Fall trifft aber auf unser Beispiel nicht zu, da wir ja run zurzeit den Wert false zu gewiesen haben. Wenn wir nun die Bedinung auswerten sehen wir !run (istAusgewertet)-> !false (istAusgewertet)-> true nun ist dieser Ausdruck true und der Scheifenkörper wird ausgeführt.

Und wenn nun alle Befehle im Schleifenkörper ausgeführt wurden springt das Programm wieder an den Anfang der whileSchleife und überprüft wieder ob die Bedingung erfüllt ist (also Ausgewertet true ergibt) Dies wird solange wiederholt, solange bis zum Ersten mal die Bedingung false ergibt und das Programm alles Ausführt, was nach der Schleife steht.

 

[Mr.Pink!]

Also heißt das zusammengefasst, dass ich bei booleschen Variablen in Schleifen immer vom true ausgehe, egal ob die Variable vorher nun false oder true war, und dementsprechend meine Bedingung formuliere?

 

[SlaterB]

'Variablen', 'ausgehen', 'egal ob' usw. sind komische Begriffe die du da verwendest, im Grunde hast du es wohl richtig verstanden aber machst dir das alles zu kompliziert, das ist doch nur Syntax

wann kann man durch eine Tür durchgehen? wenn sie offen ist,
ob der Code dazu nun [c]if (tuerOffen) [/c] oder [c]if (!tuerGeschlossen) [/c] lautet, ist doch nebensächlich..

 

[timbeau]

Zusätzlich ist einfach darauf zu achten, dass der Ausdruck

false

mit dem !-Operator zu einem neuen boolschen Ausdruck

!false

kombiniert wird.

Diesen neuen Ausdruck wertet wiederrum die Schleife aus.

Es könnte ja auch mehrere Ausdrücke geben, ganz dummes Beispiel:

if(!AmpelRot && StrasseFrei) { gib gas }

 

[Mr.Pink!]

Alles klar Jungs, habe meinen "Verständnisfehler" gefunden.

Schöne Feiertage!

Danke und lG