Selection Sort in Java?
Ich versuche seit über einer Stunde vergeblich den folgenden Pseudocode in Java zu implementieren, vielleicht kann mir ja jemand weiterhelfen.
2 Antworten
Zeige deinen aktuellen Stand, poste ihn bspw. via pastebin.
Als Zwischenschritt bei der Übersetzung in Java-Code kann es hilfreich sein, einen Programmablaufplan zu zeichnen (erweitere diesen ruhig um ein Schleifenelement), denn dieser nähert sich den einfachen Kontrollstrukturen, die dir in Java zur Verfügung stehen, noch einmal weiter an.
Ebenso hilfreich, zum Verständnis: Spiele den Ablauf nach. Nimm dir ein Zufallsarray:
[ 3, 7, 4, 0, 1 ]
Gehe Schritt für Schritt durch den Algorithmus und schreibe dir das Ergebnis von jedem Zwischenschritt auf.
Spontan fällt mir hier auf, dass die Zeilen "vertausche A[min] und A[links]" sowie "links = links + 1" fehlen.
Ja, das meine ich ja, ich weiß nicht, wie ich das tauschen implementieren soll.
Am besten geht das mit einer Hilfsvariable. Einen der Werte speicherst du in dieser ab, dann kannst du diesen Wert im Array überschreiben.
Wenn ich z.B. schreibe
int hilfe = A[i];
dann wird mir gesagt, dass die Variable i nicht deklariert ist, soll ich diese dann einfach als Klassenavariable deklarieren und dann "int" von int i, in der for-schleife entfernen?
i existiert nur innerhalb des for-loops. Wenn du versuchst außerhalb darauf zuzugreifen, geht das nicht mehr - sie wird wieder gelöscht, sobald du den for-loop wieder verlässt.
Ich würds wahrscheinlich wirklich einfach als Klassenvariable deklarieren. Du musst dir dann halt überlegen, wo im Code du "hilfe" dann einen neuen Wert zuweist.
Stell dir vor, du hast zwei Gläser vor dir stehen. Eines ist mit blauer Flüssigkeit gefüllt und eines mit roter. Du sollst nun den Inhalt der Gläser tauschen. Überlege dir die einzelnen Teilschritte, die notwendig sind, um das Problem zu lösen.
EDIT: Ok, ich sehe, du hast es schon.
Wie gesagt, an dem Punkt ist die Variable i schon wieder gelöscht, deshalb hast du da keinen Zugriff mehr darauf. Sie existiert nur hier, innerhalb des Loops:
- for(int i = links + 1 ;i < A.length; i++)
- {
- if( A[i] < A[min])
- {
- min = i;
- }
- }
Wie gesagt, deklariere "hilfe" vorher, und weiße der Variable an passender Stelle den jeweils neuen Wert zu.
aber die Variable i ist doch diesmal als Klassenvariable deklariert
Wie bekomme ich es nun hin, dass mehr als nur die 7 an den Anfang sortiert wird?
Du solltest nirgendwo eine Klassenvariable benötigen. Schau dir den Pseudocode in deinem Code an. Es gibt nur lokale Variablen.
In deinem Code wird i zudem durch die Variable i überdeckt, die in der Schleife deklariert wird.
Du hast beim Sortierverfahren grundlegend zwei Schleifen (ich richte mich jetzt nicht nach dem Algorihtmus in deinem Buch, sollte es spezifische Unterschiede geben).
Eine Schleife durchläuft deine komplette Liste. Bei jeder Iteration greift sie sich den Wert heraus, der gerade passiert wird. Eine zweite, innere Schleife dient nun dazu, den aktuellen Wert an die richtige Stelle sortieren.
Das heißt, sobald z.B. deine 7 (in dem Fall der aktuelle Wert) von der inneren Schleife richtig einsortiert wurde, geht es mit dem nächsten Wert weiter, den die innere Schleife wählt.
Ich habe mir gerade noch einmal den Algorithmus aus deinem Buch angeschaut und denke, dass die Erklärungen auf Wikipedia vermutlich besser sind.
Weißt du denn was der Algorithmus macht? Das ist der erste Schritt. Ich bin jetzt nicht sicher, hört sich an als würdest du noch versuchen einfach den Pseudocode in Code umzuwandeln, ohne zu wissen was er eigentlich machen soll.
Schreib mal, was denkst du denn das hier gemacht werden soll?
Es wird jedesmal nach der kleinsten Zahl gesucht, die wird dann mit der ersten Stelle der unsortierten Liste getauscht, bis sich alle Zahlen in der richtigen Reihenfolge sind.
Genau. Ich hab dir oben eh zu deinem Code schon was geschrieben.
Der Link funktioniert leider nicht, leitet mich zu nur zu der normalen pastebin Seite.
bin jetzt so weit (jetzt beim tauschen verstehe ich das aber nicht):
public class SelectionSort
{
// Instanzvariablen - ersetzen Sie das folgende Beispiel mit Ihren Variablen
int [] A = new int[] {8,15,3,12,9,7};
int n = A.length;
int links, min;
/**
* Konstruktor für Objekte der Klasse SelectionSort
*/
public SelectionSort()
{
// Instanzvariable initialisieren
while (links < n)
{
min = links;
for(int i = links + 1 ;i < A.length; i++)
{
if( A[i] < A[min])
{
min = i;
}
}
}
}
}