[Java] Bubblesort: Wo ist mein Fehler?

[Murhagh]

Hallo Leute,

in meinem kleinen Bubblesort-Programm soll ein Array sortiert werden. Das klappt soweit auch. Leider aber auch nur fast. Ein Wert wird nicht richtig sortiert und anscheinend bin ich zu blöd und zu blind um den Fehler zu finden. Ich habe mir schon einige Muster-Bubblesort-Lösungen angeschaut, sehe aber meinen Fehler nicht. Hoffe, dass jemand da einmal flux drüber gucken kann und mir meinen Fehler sagt.


public class SortArray{

public static void printArray(int[] a){
for (int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}

public static int[] bubblesort(int[] a){
int i = a.length;
int hilf;
int j;

if(i <= 0){
System.out.println("Ende.");
}

for(i = 0; i < a.length; i++){
for (j = 0; j <= (i-1); j++){
if(a[j] > a[j+1]){
hilf = a[j];
a[j] = a[j+1];
a[j+1] = hilf;
}
}
}
return a;
}

public static void main(String[]args){
int n = Integer.parseInt(args[0]);
int[] a = new int[n];

for (int i = 0; i < a.length; i++){
a[i] = (int)(Math.random() * 100);
}

printArray(a);
a = bubblesort(a);
printArray(a);
}
}



Vielen Dank!

[Trap]

Ich kenn Bubblesort nur mit einer einzelnen while-Schleife, wo hast du die geschachtelten for-Schleifen her?

So wie du die for-Schleifen geschrieben hast kann es nicht funktionieren. Die innere Schleife bewegt einen zu kleinen Wert maximal um eins nach links, wird aber für den letzten Wert nur genau 1 mal ausgeführt.

[Coda]

Hm? Bubblesort ist O(n²) und hat zwei Schleifen.

[Trap]

Stimmt, hab die innere Schleife vergessen zu zählen.

Ich kenn es so:
sorted=false;
while(!sorted) {
sorted=true;
for(...){
if(...){sorted=false;...}
}
}
Man kann es natürlich auch mit 2 for-Schleifen schreiben, aber die müssen dann schon n² Durchläufe ergeben, nicht nur n*n/2.

[Monger]

Ich weiß das ist nicht die Frage, und ich krieg für diesen Einwand jetzt sicher (und völlig zu Recht) ein paar böse Kommentare, aber:

Warum zur Hölle implementierst du in Java einen Bubble Sort? Doch hoffentlich wegen einem übereifrigen Lehrer/Dozenten, und nicht etwa aus eigenem Antrieb? ;)

[Murhagh]

Ich weiß das ist nicht die Frage, und ich krieg für diesen Einwand jetzt sicher (und völlig zu Recht) ein paar böse Kommentare, aber:

Warum zur Hölle implementierst du in Java einen Bubble Sort? Doch hoffentlich wegen einem übereifrigen Lehrer/Dozenten, und nicht etwa aus eigenem Antrieb? ;)


Vollkommen richtig. Unser Dozent fand anscheinend, dass es eine gute Möglichkeit ist uns einen Sortieralgorithmus in Java beizubringen.
Im Anhang ist ein Teil der Aufgabenstellung.

[Murhagh]

Nachtrag:
Den Tipp mit den 2 for-Schleifen hab ich im Internet gefunden. Genauer habe ich diese Datei gefunden:

[Monger]

Machen wir doch mal ne genaue Umsetzung deiner Aufgabe:


// schreiben sie eine Funktion bubbleSort, die ein Array entgegennimmt
public void bubbleSort(int[] A){

// setze i auf A.Length
int i = A.length;

// Falls i kleiner oder gleich null, beende die Funktion
while(i > 0){
// setze j auf 0
int j = 0;
// falls j größer oder gleich i - 1 ist, gehe zu Punkt 8
while (j < i -1){
// Vertausche A[j] mit A[j+1], falls größer
if(A[j] > A[j+1]){
int hilf = A[j];
A[j] = A[j+1];
A[j+1] = hilf;
}
// erhöhe den Wert j um eins
j++;
// gehe zu Punkt 4
}
// verringere den Wert i um eins
i--;
// Gehe zu Punkt 2
}

}


Das ist jetzt wirklich eine 1:1 Übersetzung deiner Aufgabenstellung. Funktioniert die? Habs jetzt nicht nachgeprüft.
Du brauchst übrigens dir dein Array nicht wieder zurückgeben lassen. Du arbeitest ja direkt auf dem Objekt, d.h. du sortierst ja genau das Array was du in die Methode reinstopfst.

[Murhagh]

...
Das ist jetzt wirklich eine 1:1 Übersetzung deiner Aufgabenstellung. Funktioniert die? Habs jetzt nicht nachgeprüft.
Du brauchst übrigens dir dein Array nicht wieder zurückgeben lassen. Du arbeitest ja direkt auf dem Objekt, d.h. du sortierst ja genau das Array was du in die Methode reinstopfst.


Hi Monger,

danke! Deine Umsetzung läuft 1a. Ich habe nur wieder einen Rückgabetyp eingebaut, da dieses kleine Programm noch nicht mit Objekten (außer man sieht Arrays als Objekte) arbeitet. Vielen Dank. Jetzt muss ich das nur noch verstehen, warum es mit deiner while-Schleife läuft und mit meiner 2ten for-Schleife nicht.

[redfalcon]

Vollkommen richtig. Unser Dozent fand anscheinend, dass es eine gute Möglichkeit ist uns einen Sortieralgorithmus in Java beizubringen.
Im Anhang ist ein Teil der Aufgabenstellung.

Da ist noch nichtmal ne Ausgabe gefordert? :|

Hier mal meine (kommentierte) Lösung, die wir mal für die Schule schreiben sollten:


public class BubbleSort{

public int[] array = new int[6];
public int temp;
public double randomtemp;
public char again;

public void fill(){
//Array mit Zufallszahlen füllen.
System.out.println("\n");
for(int x=0; x<array.length; x++){
//Array mit Zufallszahlen füllen
randomtemp=Math.random()*100;
randomtemp=(int)(randomtemp=randomtemp+1);
array[x]=(int)randomtemp;
System.out.println("Ungeordnetes Array-Element "+x+": "+ array[x]);
}
this.sort();
}

public void sort() {
int temp = 0;
for(int h=0; h<array.length-1; h++) {
for (int i=0; i<array.length-h-1; i++) {
// Wenn das aktuelle Element größer ist als das nächste..
if(array[i] > array[i+1]) {
//..kopiere das aktuelle Element in eine temporäre Variable.
temp = array[i];
//Kopiere den Wert des nächsten Elements in das aktuelle Element..
array[i] = array[i+1];
//..und kopiere den Wert aus der temp. Variable in das nächste Element.
array[i+1] = temp;
}
}
}
this.ausgabe();
}

public void ausgabe(){
//Ausgabe des geordneten Arrays
System.out.println("\n\n");
for(int x=0; x<array.length; x++){
System.out.println("Geordnete Daten aus Array-Element "+x+": "+ array[x]);
}
this.restart();
}

public void restart(){
// Programm nochmal starten?
System.out.println("\n\nProgramm neustarten? (y/n)");
again=StdIn.charInput();
if(String.valueOf(again).equalsIgnoreCase("y")) this.fill();
if(String.valueOf(again).equalsIgnoreCase("n")) System.exit(1);
else this.restart();
}

public static void main (String args[]){
BubbleSort bsort=new BubbleSort();
bsort.fill();
bsort.sort();
bsort.ausgabe();
bsort.restart();
}
}


Die Methode nimmt zwar das Array nicht entgegen, aber dass ist wohl auch nicht Sinn deiner Übung.

[Monger]

Jetzt muss ich das nur noch verstehen, warum es mit deiner while-Schleife läuft und mit meiner 2ten for-Schleife nicht.

Ich glaub, ich weiß warum.

Wenn man sich die beiden Zeilen aus deinem und meinem Programm mal ansieht:


for (j = 0; j <= (i-1); j++){


while (j < i -1){

dann sagen die nicht das selbe aus.

[Murhagh]

Da ist noch nichtmal ne Ausgabe gefordert? :|



Vielen Dank für dein Programm.
Wie gesagt, dass ist nur ein Ausschnitt der Aufgabenstellung. Eine Ausgabe ist schon gefordert. Es war auch gefordert, dass das Array an die Funktion übergeben wird. Leider konnte ich die Aufgabe nicht vollständig als Bild exportieren, da es immer größer als 32KB geworden ist.


Ich glaub, ich weiß warum.

Wenn man sich die beiden Zeilen aus deinem und meinem Programm mal ansieht:


for (j = 0; j <= (i-1); j++){


while (j < i -1){

dann sagen die nicht das selbe aus.


Tun sie nicht? Ich bin nun wirklich keine Leuchte im Programmieren, aber bis auf das Erhöhen von j sieht es für mich so aus, als würden sie die gleiche Funktion haben.

[Monger]

Tun sie nicht? Ich bin nun wirklich keine Leuchte im Programmieren, aber bis auf das Erhöhen von j sieht es für mich so aus, als würden sie die gleiche Funktion haben.

< ist nicht das selbe wie <= ;)
Deine Schleife macht einen Durchlauf mehr als meine.

[Murhagh]

< ist nicht das selbe wie <= ;)
Deine Schleife macht einen Durchlauf mehr als meine.


Ok, dass stimmt natürlich. Aber irgendwie scheint mein Programm eh nicht so zu laufen, wie es soll. Die zweite for-Schleife ist nicht das wahre für diesen Algorithmus.

[Trap]

Wenn man die innere Schleife mit j<i-1 schreibt muss man bei der äußeren Schleife rückwärts zählen.

[Murhagh]

Wenn man die innere Schleife mit j<i-1 schreibt muss man bei der äußeren Schleife rückwärts zählen.


Hab versucht. Dann sortiert er gar nicht mehr.


for(i = a.length; i < a.length-1; i--){
for (j = 0; j <= (i-1); j++){
if(a[j] > a[j+1]){
hilf = a[j];
a[j] = a[j+1];
a[j+1] = hilf;
}
}
}

[Trap]

for(i = a.length; i > 0; i--), die Schleifenbedingung muss man schon mitändern ;)

[Murhagh]

for(i = a.length; i > 0; i--), die Schleifenbedingung muss man schon mitändern ;)


Verdammt...danke! Jetzt läuft es auch mit den zwei for-Schleifen. :redface: