OOP Selection Sort - Ausgabe der einzelnen Schritte / zweidimensionales Array

Sigurdrifa

Mitglied
Hallo ihr Lieben,

aus lauter Verzweiflung habe ich mich nun hier angemeldet und hoffe auf Unterstützung.
Ich habe einen Info-Studiengang begonnen, bei dem es hieß, seine Veranstaltungen seien auch ohne Vorkenntnisse ... zu verstehen - Nun, wie es immer so ist, habe ich mal wieder Pech gehabt.

Meine dritte Hausaufgabe bereitet mir nun riesige Probleme, da ich gerade erst mit Java oder allgemein Programmieren begonnen habe (sprich: nur wenig Kenntnis).

Und zwar geht es um Selection Sort. Wir haben das zwar in der Vorlesung angesprochen... und dann kommt das große Aber.

Meine Hausaufgabe sieht folgendermaßen aus
Java:
public class Functionality {
	/**
	 * Sortiere a mit Selektionsort und dokumentiere den Zustand nach jedem
	 * Sortierschritt in der Rückgabe. Suche immmer das neue Minimum.
	 * 
	 * @param a
	 *            zu sortierendes Array
	 * @return Die Zustände der Sortierung
	 */

	public static int[][] selectionsort(int[] a) {
		return null;
	}

}


Quasi muss ich die Lücken füllen. Mir fehlt ein Ansatz... ich versteh es einfach nicht, wie ich das auf Zweidimensionalität übertragen soll... Um ehrlich zu sein, weiß ich nichts und bin mega frustriert :'(

Falls es hilft, anhängig war noch eine Public Test Datei
Java:
import static org.junit.Assert.assertArrayEquals;

public class PublicTests {
	public static void main(String[] args) {
		int[] a = new int[] { 35, 7, 63, 42, 24, 21 };
		int[][] b = new int[][] { new int[] { 7, 35, 63, 42, 24, 21 },
				new int[] { 7, 21, 63, 42, 24, 35 },
				new int[] { 7, 21, 24, 42, 63, 35 },
				new int[] { 7, 21, 24, 35, 63, 42 },
				new int[] { 7, 21, 24, 35, 42, 63 },
				new int[] { 7, 21, 24, 35, 42, 63 } };
		int[][] c = Functionality.selctionsort(a);
		for (int i = 0; i < 6; i++)
			assertArrayEquals(b[i], c[i]);
	}

}
 

Flown

Administrator
Mitarbeiter
Du hast da was falsch verstanden. In jeder Zeile soll ein Sortierschritt gespeichert werden.

in: [3, 1, 2]
out:
[1, 3, 2]
[1, 2, 3]
[1, 2, 3]

Das heißt in der ersten Zeile sortierst du die 1-te Stelle bei der zweiten 2-Stelle usw.
 

Flown

Administrator
Mitarbeiter
Implementiere doch mal den Selectionsort-Algorithmus, dann kann ich dir dann weiterhelfen.

[edit] Habe den Thread ins richtige Unterforum verschoben[/edit]
 
Zuletzt bearbeitet:

rme

Top Contributor
Keine Panik :) Es ist am Anfang des Studiums ganz normal, dass man nicht gleich gut klarkommt und mit einigen Veranstaltungen Probleme hat. Das wird anderen auch so gehen - nur zeigt es niemand gern, schließlich denkt man, dass man der einzige ist, der es nicht verstanden hat und schämt sich dann oder so..

Hast du den generellen Ansatz von SelectionSort denn verstanden? Also kannst du in deinen Worten beschreiben, wie der Algorithmus funktioniert? Wenn du einzelne Schritte in deinen Worten beschreiben kannst, fällt es leichter, die Einzelschritte dann nach Java zu übertragen.

Das mit den 2 Dimensionen ist erstmal nicht so wichtig, sortiert werden soll ja trotzdem nur eine Dimension. Das andere kannst du machen, sobald du das erste Problem gelöst hast.. das ist vielleicht etwas motivierender :)
 

Sigurdrifa

Mitglied
Wie das ganze funktioniert, verstehe ich voll und ganz... Implementiert hätte ich das folgendermaßen:

Java:
public static void selectionsort(int[] a) {	
			for (int i = 0; i < a.length; i++) {
				int minimum = i;
				for (int j = i + 1; j < a.length; j++);
					if (a[i] < a[minimum])
						minimum = j;
					
						if (minimum != i) {
							int swap = a[i];
							a[i] = a[j];
							a[j] = swap;
						}	
								
				}
			}

Ich scheine da aber auch schon einen Fehler zu haben. Mein Eclipse meckert 'j cannot be resolved to avariable'

Was dabei passiert - ist ja einfach auszudruecken und das kann ich auch so jemandem erklaeren, aber was ich beim implementieren nun falsch mache .... keine Ahnung X__x und jetzt dann noch die Überforderung in der HA mit int [][].

Ich fluche den ganzen Tag GRRRR
 

rme

Top Contributor
In Zeile 4 hast du ein Semikolon hinter die for-Schleife gesetzt - dadurch hast du einen leeren Schleifenkörper, d.h. die Schleife führt die leere Anweisung hintereinander aus. Und hinter er Schleife endet der Gültigkeitsbereich von j, deshalb die Fehlermeldung.

Das passiert einem am Anfang ab und zu, weil die Syntax ungewöhnlich ist :) Mal Semikolon, mal nicht.. Stattdessen sollte da in diesem Fall ein { stehen, um den Schleifenkörper zu beginnen.

Das zweidimensionale ist nur für die Rückgabe - da sollst du in jedem Schritt speichern, wie deine Folge in dem Schritt aussah. Also in Dimension 1 die Schrittnummer und in Dimension 2 deine gesamte Folge. Dazu könntest du eine neue Schleife am Ende von jedem Schritt einfügen, die die Folge in das Rückgabe-Array kopiert.
 
Zuletzt bearbeitet:

Sigurdrifa

Mitglied
Ja, die lieben Syntaxfehler.

Habe ich das denn auch ''Programmiertechnisch'' richtig verstanden:
Schritt 1 endet beim ersten if oder? Schritt 2 nach dem swap?
 

rme

Top Contributor
Mit Schritt ist normalerweise eine Iteration der äußeren Schleife gemeint, also endet Schritt 1 in Zeile 14 des obigen Codes und alle anderen Schritte ebenfalls.

Schritt 1 überführt die Folge 35, 7, 63, 42, 24, 21 nach 7, 35, 63, 42, 24, 21 und Schritt 2 nach 7, 21, 63, 42, 24, 35. Die Anzahl der Schritte hängt also nur von der Länge der Eingabe ab, nicht von deinem konkreten Code.
 

Flown

Administrator
Mitarbeiter
So jetzt geht dir am Anfang deines selectionsorts noch soetwas ab:
Java:
int[][] results = new int[a.length][a.length];

Und nach dem Swap:
Java:
System.arraycopy(a, 0, results[i], 0, a.length);

Wahlweise auch:
Java:
results[i] = Arrays.copyOf(a, a.length);
 

rme

Top Contributor
Flown: Ich denke, dass diese beiden Methoden in Anfängerübungen verboten sind - es geht ja darum, dass man etwas über Schleifen und Arrays lernt.. also ich hätte als Übungsleiter keine Punkte dafür gegeben :)
 
Zuletzt bearbeitet:

Sigurdrifa

Mitglied
Okay, das kenn ich auch noch gar nicht mit dem copy :)
Kannst du mir sagen, was die 0 bei deinem code nach dem swap genau bedeutet? Dass er bei i und j = 0 anfängt durchzulaufen?
 

rme

Top Contributor
Die Parameter von arrayCopy sind: Quelle, StartIndex der Quelle, Ziel, StartIndex des Ziels, Anzahl der zu kopierenden Elemente. Aber wenn du das nicht aus der Vorlesung kennst, sollst du das bestimmt mit einer eigenen Schleife machen ;)
 

Sigurdrifa

Mitglied
heieieieieiei xD Probleme, Probleme. Jetzt weiß ich wirklich nicht mehr weiter :p

Hinzu kommt noch, dass 'run' nicht greift. Obwohl ich beide classes (Die Aufgabe und die Public Tests) in meinem Projekt hab. Meh. "There are no recent launches"
 

Sigurdrifa

Mitglied
Java Projekt OOPM > src > default package > Functionality.java

Java:
public class Functionality {
	/**
	 * Sortiere a mit Selektionsort und dokumentiere den Zustand nach jedem
	 * Sortierschritt in der Rückgabe. Suche immmer das neue Minimum.
	 * 
	 * @param a
	 *            zu sortierendes Array
	 * @return Die Zustände der Sortierung
	 */

		public static void selectionsort(int[] a) {	
		    int[][] results = new int[a.length][a.length];
			for (int i = 0; i < a.length; i++) {
				int minimum = i;
				for (int j = i + 1; j < a.length; j++) {
					if (a[i] < a[minimum])
						minimum = j;
					
						if (minimum != i) {
							int swap = a[i];
							a[i] = a[j];
							a[j] = swap;
						}System.arraycopy(a, 0, results[i], 0, a.length);	
				}				
			}
		}
	}

Wo ich ja nochmal mit dem copy überlegen muss.

und unter
OOPM > Referenced Libraries > PublicTests.java
Das ist ja immer vorgefertigt und stellt mir keine Aufgabe

Java:
import static org.junit.Assert.assertArrayEquals;

public class PublicTests {
	public static void main(String[] args) {
		int[] a = new int[] { 35, 7, 63, 42, 24, 21 };
		int[][] b = new int[][] { new int[] { 7, 35, 63, 42, 24, 21 },
				new int[] { 7, 21, 63, 42, 24, 35 },
				new int[] { 7, 21, 24, 42, 63, 35 },
				new int[] { 7, 21, 24, 35, 63, 42 },
				new int[] { 7, 21, 24, 35, 42, 63 },
				new int[] { 7, 21, 24, 35, 42, 63 } };
		int[][] c = Functionality.selctionsort(a);
		for (int i = 0; i < 6; i++)
			assertArrayEquals(b[i], c[i]);
	}

}
 

Flown

Administrator
Mitarbeiter
Du hast den Rückgabewert deiner Methode geändert, es muss das 2D-Array zurückgeben.

Normalerweise sollte man schon lernen, dass Arrays kopieren durch das OS passieren soll, da es das viel performanter schafft.

Aber um es händisch zu machen musst du dir ein Array anlegen mit der gleichen Länge wie a und dann über a drüberiterieren und den Wert an jeder Stelle dem neuen Array zuweisen.
 

rme

Top Contributor
Das Kopieren ist glaube ich an einer falschen Position, darüber musst du nochmal nachdenken.. es befindet sich momentan ja innerhalb der inneren Schleife, die das Minimum sucht. Dort kopierst du jetzt jedesmal einen Schritt in das Ausgabearray.

Aber das Starten sollte trotzdem klappen oder einen Syntaxfehler zeigen, nicht aber die obige Meldung - denn die PublicTests-Datei enthält ja eine main-Methode und hat keine Syntaxfehler. Klappt es, diese Datei zu starten? Je nachdem, mit welcher Umgebung du programmierst, kannst du manchmal nur die Datei mit main starten und manchmal ist es egal, da die Umgebung das ganze Projekt kennt.
 
Zuletzt bearbeitet:

Sigurdrifa

Mitglied
Das Kopieren habe ich ja wie gesagt noch nie benutzt, deshalb weiß ich nicht, was ich da alternativ benutzen kann. ich sehe halt in den Tests ein a-array und ein b-array...

Nein, das PublicTests starten klappt auch nicht "Editor does not contain maintype" - Ich benutze Eclipse Luna.
 

Flown

Administrator
Mitarbeiter
Dein SelectionSort funktioniert auch noch nicht richtig. Deine innere Schleife ist nur zum Minimum(index) finden gedacht und es sollte erst nach dieser Schleife sortiert werden. Darum hat der Algorithmus auch eine Komplexität von O(n²)
 

Sigurdrifa

Mitglied
Ach Fehler gefunden, der doppelklick auf's Projekt hatte gefehlt... Run funzt aber "Fehler: Hauptmethode in Klasse Functionality nicht gefunden. Definieren Sie die Hauptmethode als:
public static void main(String[] args):
oder eine JavaFX-Anwendung muss javafx.application.Application erweitern" - Normalerweise funzten die Hausaufgaben aber immer ohne main ... wegen der Tests AAAAH
 

Sigurdrifa

Mitglied
Okay, dann model ich gleich mal mit nem neuen Projekt rum :) Ist ja schonmal gut, dass es bei anderen klappt

Das einzige Problem, was ich jetzt noch habe, dieses Copy zu ersetzen ^^''
Ich weiß nicht recht, wie ich das in Schleifen ausdrücken soll und ob ich dann ein neues array b brauche... Da hört es leider Gottes bei mir auf :(
 

Flown

Administrator
Mitarbeiter
Pseudocode:

Code:
array = new[len(a)]
for: 0...len(a):
   array[i] = a[i]
end for
 
Zuletzt bearbeitet:

Sigurdrifa

Mitglied
Ich Blödmann habe die erste Zeile abgeändert.... Das darf ich ja gar nicht...
Jetzt funktioniert mein ganzes Progi auch nicht mehr mit der Zeile vom Prof

Java:
public static int [][] selectionsort(int[] a) { .....
 

Oben