Frage von iParadox15, 118

Kann mir jemand diesen Java-Code für das Bubble Sort Verfahren erklären?

Hi, kann mir jemand diesen Java Code für das Bubble Sort Verfahren in Bezug auf folgende Fragen erklären?

public class BubbleSort { 
public static void sortiere(int[] x) {
  boolean unsortiert=true;
  int temp;
  
  while (unsortiert){
     unsortiert = false;
     for (int i=0; i < x.length-1; i++) 
        if (x[i] > x[i+1]) {                      
           temp       = x[i];
           x[i]       = x[i+1];
           x[i+1]     = temp;
           unsortiert = true;
        }          
  } 
}

public static void main(String[] args) {
  int[] liste = {0,9,4,6,2,8,5,1,7,3};
  sortiere(liste);
  for (int i=0; i<liste.length; i++) 
     System.out.print(liste[i]+" ");    
   } 
}

Der Code entstammt von dieser Seite: http://www.java-uni.de/index.php?Seite=85 Dort wird er aber nicht erklärt.. - Was bedeutet der Befehl "boolean"? - Was meint man mit int temp? - Wie läuft die while-Schleife ab, wenn innerhalb davon eine for-Schleife und innerhalb davon verschiedene if-Bedingungen aufgelistet sind?

Ich hoffe jemand nimmt sich die Zeit. Wär Euch sehr dankbar. :)

Antwort
von mirolPirol, 61

boolean ist kein Befehl, sondern ein Datentyp, ein Wahrheitswert, der kann ja oder nein sein (englisch true oder false)

In der Funktion "sortiere()" wird der Wahrheitswert "unsortiert" auf true gesetzt, denn sonst wäre die Funktion sofort abgearbeitet, weil sie genau so lange läuft, bis unsortiert = false ist, also alles korrekt sortiert ist.

Die Integerwert-Liste besteht aus 10 Elementen (Ziffern), in Java hat das erste Element immer den Index 0. Es gibt also die Elemente liste[0]...liste[9].

Solange der Zähler i < 9 wird i incrementiert, also um 1 erhöht und dann geguckt, ob das Element i größer ist als das folgende Element i+1, denn in dem Fall muss das Element i+1 an die Stelle des Elementes i. Die Integervariable "temp" wird als Zwischenspeicher benutzt, um sich den Wert vom Element i zu merken, weil es ja mit dem Wert vom Element i+1 überschrieben wird.

Diese Schleife wird nun 10x durchlaufen, danach stehen alle Elemente in der korrekt sortierten Reihenfolge im Integerarray "liste" und werden jetzt nur noch mit je einem Leerzeichen getrennt am Bildschirm angezeigt.

Ich hoffe, du hast ein wenig vertanden...

Kommentar von iParadox15 ,

Hey, danke für die ausführliche Antwort. Sorry wenn ich mich zu doof anstelle, aber kannste mir diese 4 if-Bedingungen nochmal einzelt erklären?

 1. temp = x[i];
2. x[i] = x[i+1];
3. x[i+1] = temp;
4. unsortiert = true;

Das Prinzip verstehe ich. Ist ja recht simpel. Aber anhand des Codes nicht...

Kommentar von procoder42 ,

Die beiden Variablen werden getauscht (dafür braucht man die temporäre Variable)

Kommentar von mirolPirol ,

Klar, das sind keine 4 if-Bedingungen, sondern wenn die if-Bedingung erfüllt ist, also 

x[i] > x[i+1] = true,

dann werden diese 4 Zuweisungen abgearbeitet:

1. Merke den Wert von x[i] in der Variablen temp

2. Schreibe den Wert von x[i+1] in das Element x[i]

3. Übergebe den in temp zwischengespeicherten Wert an x[i+1]

4. Setze unsortiert wieder auf true, denn wir sind noch nicht fertig.

Antwort
von RedKungFuMastr, 46

Die visuelle Ansicht von Bubblesort (Wikipedia):

https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gi...

Was im Code passiert:

// wenn unsortiert == true => wiederhole
while( unsortiert )
{
 // Array wird als sortiert deklariert
 unsortiert = false;
 // x.length == Anzahl der Felder im Array
 // solang Variable i kleiner als x.length
 // => wiederhole; addiere nach dem
 // Vorgang 1 zu i (i++)
 for(int i=0; i<x.length-1; i++)
  // ist die Zahl im Array x auf der Position i
  // größer als im Array x auf der nächsthöheren
  // Position nach i, dann führe aus..
  if(x[i] > x[i+1])
  {
   // Rekursion:
   // Nehme temporäre Variable temp und weise dieser
   // der Zahl in x auf Position i zu 
temp = x[i];
   // Überschreibe die Zahl in x auf Pos. i
   // mit der Zahl in x auf Pos, i+1
   x[i] = x[i+1];
   // Überschreibe x[i+1] mit der Temporären Variable
   x[i+1] = temp;
   // falls diese IF-Anweisung ausgeführt wurde
   // deklariere das Array als unsortiert
   // damit die WHILE-Schleife sich wiederholen kann
  }
 // Ist das Array sortiert, dann ist
 // unsortiert == false
 // => trifft dies zu, endet die WHILE-Schleife
}
Kommentar von RedKungFuMastr ,

in der IF-Anweisung hab ich das

unsortiert = true;

vergessen, sry ^^

Antwort
von sarahj, 21

da Du offensichtlich erst mal die Basics von java brauchst, hier eine sehr kurze Definition der Zeilen. Du solltest aber unbedingt nochmal ganz von vorne anfangen, und ein Lehrbuch zur Hand nehmen. Um code zu verstehen sollte das schon "drin" sein...

boolean unsortiert=true;

definiert eine lokale Variable mit Namen "unsortiert", und mit Typ "boolean" und gibt ihr den initialen Wert "true".

int tmp;

definiert eine weitere lokale Variable, mit default Wert. (0 bei int).

boolean sind die logischen Werte true/false;
int sind ganze Zahlen (Wertebereich -2^31..2^31-1).

while (bedingung) { anweisungen }

solange "bedingung" gleich true ist, werden alle Anweisungen in den geschweiften Klammern wiederholt.
ACHTUNG: eigentlich kommt hinter "while" (oder "for" oder "if") nur eine Anweisung. Das heisst, "while" wiederholt eine Anweisung, solange die Bedingung erfüllt ist.
ABER: mit "{"..."}" kann man mehrere Anweisungen zu einem Block zusammenfassen, und die gelten dann wie eine Anweisung hinter "while", "for", "if" etc.
Dazu solltest Du dir nochmal die Syntax (Gramatik) der Sprache Java anschauen (Lehrbuch).

Da hinter dem "while" ein Block mit mehreren Anweisungen kommt, werden alle darin nacheinander in der Schleife ausgeführt.

unsortiert = false;

sollte klar sein.

for (int i=0; i < x.length-1; i++)

eine weitere lokale Variable "i" mit Typ "int" wird definiert, und die nachfolgende Anweisung mit mehrmals durchlaufen, wobei "i" nacheinander die Werte 0..x.length-1 annimmt. Die 3 Ausdrücke in der "for"-Anweisung sind initializer, test und increment. "for (initializer; test; increment) anweisung" bedeutet nichts anderes als:

initializer;
while (test) {
   anweisung;
   increment
}

Beachte: hinter dem "for" kommt keine geschweifte Klammer. Es wird also nur eine Anweisung in der "for"-Schleife mehrfach ausgeführt. Die eine Anweisung ist das "if", das aber seinerseits (->Block) im true-zweig mehrere Anweisungen in einem Block hat.

Also immer merken: mit geschweiften Klammern macht man einen Block, der für das "while", "for", "if" usw. wie eine einzelne aussieht.
Wenn Du die geschweiften Klammern vergisst, wird (auch wenn es nett eingerückt ist) nur eine Anweisung ausgeführt (ein häufiger Anfängerfehler).
Ich empfehle daher immer geschweifte Klammern zu schreiben, auch wenn man nur eine einzige Anweisung in einer Schleife hat (der code wäre mit "{" in der "for"-Schleife m.E. schöner...)

Das "if" sollte klar sein: zwei aufeinanderfolgende Elemente werden aus dem Array gelesen, und verglichen. "i" ist der Index (der ja von 0 bis 2-vor-der-Länge läuft).

Die Anweisungen im "if" tauschen die beiden Elemente im Array aus, wenn das erste größer ist als das zweite.
UND (wichtig): unsortiert wird wieder auf "true" gesetzt.
Beachte nochmal, daß alle Anweisungen zum Austauschen und setzen von "unsortiert" in einem Block stehen.

Was macht das ganze?

Nehmen wir zuerst einmal an, der Array wäre schon sortiert.
Dann läuft die "while"-Schleife an, setzt "unsorted" auf false, und geht das ganze Array einmal durch, und schaut, ob da zwei Elemente in falscher Reihenfolge vorkommen. In diesem Fall (bereits sortiert) findet es kein solches Paar.
Am Ende der "for"-Schleife ist also "unsortiert" immer noch "false", und es gibt keinen zweiten Durchlauf der "while" Schleife. Fertig.

Fall 2: angenommen, die innere "for"-Schleife findet so ein "falsches Paar". Dann werden die beiden ausgetauscht, so daß jetzt das kleinere Element an index "i", und das größere an "i+1" zu liegen kommt. Und: es wird "unsorted" auf true gesetzt.
Das heisst, daß am Ende ein paar Elemente um einen Platz nach "unten" gerutscht sind. Da das aber nicht unbedingt reicht (weil u.U. Elemente noch viel weiter rutschen müssen), wird die "while"-Schleife nochmal durchlaufen. Wieder beginnend ab Index 0. Das passiert solange, bis kein "falsches Paar" mehr gefunden wurde. Dann ist das Array sortiert.

Beispiel:

0,9,4,6,2,8,5,1,7,3

nach erstem Durchlauf:

0,4,6,2,8,5,1,7,3,9

nach 2. Durchlauf:

0,4,2,6,5,1,7,3,8,9

nach 3. Durchlauf:

0,2,4,5,1,6,3,7,8,9

nach 4. Durchlauf:

0,2,4,1,5,3,6,7,8,9

5. Durchlauf:

0,2,1,4,3,5,6,7,8,9

6. Durchlauf:

0,1,2,3,4,5,6,7,8,9

7. Durchlauf:

0,2,1,4,3,5,6,7,8,9

kein Austausch mehr.

So, jetzt tun mir die Finger weh. Ich hoffe alles ist jetzt klarer.

Antwort
von SinomHD, 60

Dein Programm sortiert zahlen

Ein boolean kann wahr oder falsch sein
Ist einfach eine "Einheit" für die beiden Möglichkeiten

Der int temp ist eine "GANZ ZAHL" also ohne Komma und wird bei deinem Programm immer weiter erhöht

Antwort
von iParadox15, 19

Ich danke euch allen für eure Mühe! Hab das auf jeden Fall verstanden jetzt :)

Antwort
von procoder42, 47

Was bedeutet der Befehl "boolean"?

Boolean ist eine Datentyp. Im Deutschen würde man das als "Wahrheitswert" bezeichnen (der Wertebereich ist wahr oder falsch).

Was meint man mit int temp?

Das ist der Name einer temporären Variable

Kommentar von iParadox15 ,

Danke, so eine Antwort brauch ich. :) Kannst Du mir noch das mit der while-Schleife innerhalb davon eine for-Schleife mit if Bedinungen erklären? Ich habe kenne das nur mit for-Schleife und innerhalb davon if-Bedingungen. Bedeutet das, dass es solange wiederholt wird, bis das Array sortiert wurde?

Kommentar von PerfectMuffin ,

while(unsortiert)

Muss man ernsthaft etwas dazu sagen?

Kommentar von procoder42 ,

- Die if-Abfrage überprüft, ob die aktuelle Zahl größer als die Folgende ist. In dem Fall werden die Zahlen dann vertauscht.

- Die for-Schleife dürchläuft das Array.

- Die While Schleife läuft solange, wie das Array unsortiert ist

Antwort
von PerfectMuffin, 40

Hats du keine Lehrmaterialien dafür?

Kommentar von iParadox15 ,

Nein, ist ganz neu bei uns..

Kommentar von PerfectMuffin ,

Niemand schmeißt dir Code hin und erwartet, dass du ihn verstehst ohne dir solche Grundlagen zu erklären.

Keine passende Antwort gefunden?

Fragen Sie die Community