BubbleSort

[tootsie77]

Hallo zusammen,

ich weiss nicht, woran es liegt, aber ich bekomme von meinem Uni-ASB-System immer die Meldungen:

Fehler
Das Sortieren des Feldabschnitts [16, 17, 5, 3, 18, 14, 4, 14] sollte zu dem Ergebnis [3, 4, 5, 14, 14, 16, 17, 18] fuehren.
Ihre Loesung fuehrt zu folgendem Ergenis [4, 5, 9, 14, 14, 16, 17, 17] .

und

Fehler
Das Sortieren des Feldabschnitts [5] sollte zu dem Ergebnis [5] führen.
Ihre Loesung fuehrt zu folgendem Ergenis [9] .

für folgenden Code:

public static void bubbleSort (int [] list, int leftIdx, int rightIdx)
	{
		int tmp;
		
		if (leftIdx < 0 || leftIdx > list.length - 1 || rightIdx < 0 || rightIdx > list.length - 1)
           	throw new IllegalArgumentException();
		
		for (int i = list.length - 1; i > 0; i--)
			for (int j = 0; j < i; j++)
			{
				if (list[j] > list[j + 1]) 
				{                      
					tmp          = list[j];
					list[j]      = list[j + 1];
					list[j + 1]  = tmp;
				}          
			} 
	}

Weiss jemand, woran es scheitert? Sonst meldete es, es sei alles i.O.

Grüsse tootsie77

 

[Bananabert]

Java verwendet Call by Value.
Dein Variable list ist nur innerhalb deiner Funktion bubbleSort sortiert. Gibt die Variable list am Ende deiner Funktion zurück.

 

[tootsie77]

Hallo Bananabert,

vielen Dank für Deine schnelle Antwort, ich habe es versucht, leider ohne den gewünschten Erfolg. Vielleicht habe ich es an die falsche Stelle geschrieben, könntest Du es etwas präziser schreiben, wohin genau? Hatte es vor die letzte geschweifte Klammer geschrieben.

Danke

 

[Maggot]

Am Methoden Anfang musst du aus void ein int[] machen. Dann vor der letzten geschweiften Klammer ein return list

 

[tootsie77]

Hallo Patrick,

auch Dir vielen Dank, aber das void ist mir vorgegeben durch die Aufgabenstellung der Uni und wenn ich es verändere funktionieren die zugehörigen Methoden nicht mehr, daher kann ich es nicht mit return und int[] machen.
Noch andere Ideen?

Danke

 

[Bananabert]

Was sind denn die "dazugehörigen Funktionen" ?
Aber ohne zu wissen wie der Rest aufgerufen wird schwierig weitere Tipps zu geben.
Poste doch am Besten mal dein gesamtes Programm.
Eine Möglichkeit wäre noch list zu einer Klassenvariable zu machen.

 

[tootsie77]

Hallo zusammen,

hatte leider keine Zeit früher zu antworten. Anbei der gesamte Code und laut meines Uni-Betreuers, scheitert es nur noch an Zeile 23.

for (leftIdx = list.length - 1; leftIdx > 0; leftIdx--)

package algorithm;
import java.util.*;
public class Sort
{
	public static void bubbleSort(int[] list)
    {
		for (int leftIdx = 1; leftIdx < list.length; leftIdx++)
			for (int rightIdx = 0; rightIdx < list.length - leftIdx; rightIdx++)
			{
				if (list[rightIdx] > list[rightIdx + 1])
				{                      
					swap(list, rightIdx, rightIdx + 1);
				}  
			}
    }
	
	public static void bubbleSort(int[] list, int leftIdx, int rightIdx) 
	{
		
		if (leftIdx < 0 || leftIdx > list.length - 1 || rightIdx < 0 || rightIdx > list.length - 1)
			throw new IllegalArgumentException();
		 
		for (leftIdx = list.length - 1; leftIdx > 0; leftIdx--)
			for (rightIdx = 0; rightIdx < leftIdx; rightIdx++)
			{
				if (list[rightIdx] > list[rightIdx + 1]) 
				{                      
					swap(list, rightIdx, rightIdx + 1);
				}          
			} 
	}

	public static void bubbleUp(int[] list, int leftIdx, int i)
    {
		int tmp = list.length - 1;
		
		if (leftIdx < 0 || leftIdx > list.length - 1 || i < 0 || i > list.length - 1)
			throw new IllegalArgumentException();
 
		for (int j = leftIdx; j < i; j++)
		{
	   		if (list[j] > list[j + 1])
	   		{
	   			tmp 		= list[j];
	   			list[j] 	= list[j + 1];
	   			list[j + 1] = tmp;
    		}
	   	}
    }
public static void swap(int[] list, int rightIdx, int leftIdx)
	{
		if (leftIdx < 0 || leftIdx > list.length - 1 || rightIdx < 0 || rightIdx > list.length - 1)
			throw new IllegalArgumentException();
		
		int tmp 		= list[leftIdx];
		list[leftIdx] 	= list[rightIdx];
		list[rightIdx] 	= tmp;

	}
	
	public static String toString (int[] list, int start, int end)
	{
		int wert = end - start;
		int [] ausschnitt = new int[wert+1];
		for(int i = start; i <=end; i++)
			if (start < 0 || end < 0 ||start > end || start > list.length - 1 || end > list.length - 1)
				throw new IllegalArgumentException();

		int i = 0;
		ausschnitt[i - start] = list[i];
		System.out.print(i);
			
		String s = "list in toString(list, start, end) = " + Arrays.toString(ausschnitt);
		System.out.println("\n" + s);
		return s;

	}
	
	public static String toString (int[] list)
	{
		if (list == null)
			return "null";
		return list.length + "," + toString(list, list.length, 0);
	}

In bubbleSort() muss also im Prinzip nur noch die äußere for-Schleife umgesetzt werden, wobei Sie nicht von n bis 1, sondern von rightIdx bis leftIdx laufen müssen.(Laut meinem Uni-Betreuer).
Leider sehe ich den Wald vor lauter Bäumen nicht, kann mir einer sagen, was ich in erwähnter Zeile 23 umstellen muss, damit es funktioniert. Seine Aussage hat mich nur weiter verwirrt.
Vielen Dank im Voraus.

Grüsse Holger

 

[InfectedBytes]

Java verwendet Call by Value.
Dein Variable list ist nur innerhalb deiner Funktion bubbleSort sortiert. Gibt die Variable list am Ende deiner Funktion zurück.

Vorsicht, es ist zwar richtig, dass Java Call By Value macht, aber da es sich um ein Array handelt, wird nur die Referenz auf dieses kopiert übergeben. Wenn aber innerhalb der Funktion der Inhalt des Arrays verändert wird, so bleibt diese Änderung natürlich auch nach dem Aufruf der Funktion bestehen.

In bubbleSort() muss also im Prinzip nur noch die äußere for-Schleife umgesetzt werden, wobei Sie nicht von n bis 1, sondern von rightIdx bis leftIdx laufen müssen.(Laut meinem Uni-Betreuer).

Ich habe mir deinen Code ehrlich gesagt nicht genauer angeguckt, aber ich würde mal vermuten, dass dein Betreuer sowas meint:

for(int idx = rightIdx; idx>=leftIdx; idx--){
...
}

 

[tootsie77]

Hi InfectedBytes,

sorry, hat leider nicht das gewünschte Ergebnis gebracht. Noch ne Idee?
Das hat mein Betreuer alles geschrieben:


Das Problem ist, dass bei bubbleSort(int[] list, int leftIdx, int rightIdx) die beiden letzten Argumente immernoch nicht richtig "eingesetzt" werden.

Hier die Zeile 23 aus Sort.java:

for (leftIdx = list.length - 1; leftIdx > 0; leftIdx--)

Was hier passiert ist: Zu Beginn dieser for-Schleife bekommt die Variable leftIdx einen neuen Wert, der ursprüngliche über das Argument übergebene Wert geht verloren.

Alles was sich hier in der inneren for-Schleife befindet, haben Sie durch bubbleUp() schon korrekt implementiert. In bubbleSort() muss also im Prinzip nur noch die äußere for-Schleife umgesetzt werden, wobei Sie nicht von n bis 1, sondern von rightIdx bis leftIdx laufen müssen.

Danke schon für Eure Mühen
Gruss Holger

 

[tootsie77]

Hallo erneut, hätte noch jemand eine Idee, um mein Problem zu lösen?

Danke im Voraus