# BubbleSort (Sortieralgorithmus)



## Mr.Pink! (11. Apr 2011)

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 (11. Apr 2011)

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


----------



## Mr.Pink! (11. Apr 2011)

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 (11. Apr 2011)

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! (11. Apr 2011)

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 (11. Apr 2011)

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! (11. Apr 2011)

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! (11. Apr 2011)

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 (11. Apr 2011)

hast du meinen Beitrag oben gesehen?


----------



## jgh (11. Apr 2011)

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! (11. Apr 2011)

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 (11. Apr 2011)

Mr.Pink! hat gesagt.:


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



Mr.Pink! hat gesagt.:


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


Die Antwort findest du hier


----------



## AmunRa (11. Apr 2011)

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 (11. Apr 2011)

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


----------



## Mr.Pink! (12. Apr 2011)

AmunRa hat gesagt.:


> 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 (12. Apr 2011)

^^


----------



## AmunRa (12. Apr 2011)

```
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! (19. Apr 2011)

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 (19. Apr 2011)

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 (19. Apr 2011)

Hier noch ein kleiner Link zum lesen

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


----------



## SlaterB (19. Apr 2011)

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


AmunRa hat gesagt.:


> ```
> 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! (20. Apr 2011)

AmunRa hat gesagt.:


> 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 (20. Apr 2011)

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! (20. Apr 2011)

Hey,

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

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



AmunRa hat gesagt.:


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


----------



## AmunRa (20. Apr 2011)

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! (20. Apr 2011)

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 (20. Apr 2011)

'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 (20. Apr 2011)

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! (21. Apr 2011)

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

Schöne Feiertage!

Danke und lG


----------

