Selection sort

B

BaxterStockman

Mitglied
Hallo,

ich versuche grade einen Selection Sort Algorithmus zu programmieren, gibts nen Befehl der aus nem Array den kleinsten Integer-Wert raussucht ? irgendwas mit parseInt?

Also ich leg jetzt mit
Java: 
int [] menge = new int []{4,6,1,9,3}

ne menge fest und will diese jetzt durch gehen und das kleinste Element suchen
 
Ja gibt es in meinem eigenen Code und sieht so aus:

Java: 
	private static int sucheMin(int[] pArr) {
		int min = Integer.MAX_VALUE;
		for(int i : pArr) {
// na ja, etwas solltest du selbst noch nachdenken :-)
		}
		return min;
	}

Mach einen konstruktiven Vorschlag wie du diese Funktion implementieren würdest und ich helf dir weiter wenn sie nicht funktioniert ;-)
 
ok also die for-schleife hab ich shcon mal
Java: 
public static void sortiere (int[]array){
	array = new int []{4,6,1,9,3}; 
	int min = Integer.MIN_VALUE;
	for (int i=0;i<array.length;i++)
		min =array[1];
	
}

Das Problem ist jetzt schreibt er ja immer wieder alles an die erste Stelle, oder ? bzw. passt das überhaupt mit dem minvalue?
 
so hab sie jetzt umgeschrieben

Java: 
public static void sortiere (int[]array){
	array = new int []{}; 
	int min = Integer.MIN_VALUE;
	for (int i=0;i<array.length;i++)
		min =array[0];
		for (int j=0;j<array.length()-1;j++)
			min = array[1];



}
public static void main (String []args){
	 int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 }; 
	System.out.println(sortiere(test));
}

Das Problem ist ich bin mit nicht sicher ob das mit dem length()-1 passt weil das unterringelt wird, außerdem hab ich hierfür wieder nur die ersten zwei stellen, muss ich noch ne while schleife einbauen bis er fertig ist ?
 
Java: 
	public static void sortiere (int[]array){
	    array = new int []{}; 
	    int min = Integer.MIN_VALUE;
	    for (int i=0;i<array.length;i++)
	        min =array[0];
	        for (int j=0;j<array.length-1;j++)
	            min = array[1];
	 
	 
	 
	}
	
	public static void main (String []args){
	     int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 };
	     sortiere(test);
	    System.out.println(Arrays.toString(test));
	}

Da fehlt aber noch das sortieren... 😉
 
BaxterStockman hat gesagt.:
so hab sie jetzt umgeschrieben

Java: 
public static void sortiere (int[]array){
	array = new int []{}; 
	int min = Integer.MIN_VALUE;
	for (int i=0;i<array.length;i++)
		min =array[0];
		for (int j=0;j<array.length()-1;j++)
			min = array[1]; // Studier mal ganz genau darüber nach!



}
public static void main (String []args){
	 int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 }; 
	System.out.println(sortiere(test));
}

Das Problem ist ich bin mit nicht sicher ob das mit dem length()-1 passt weil das unterringelt wird, außerdem hab ich hierfür wieder nur die ersten zwei stellen, muss ich noch ne while schleife einbauen bis er fertig ist ?
Zum Vergrößern anklicken....

Denk erst mal über Zeile 7 nach -
die Probleme der fehlenden Deklaration sind ja mit einem Mausklick gelöst
 
Java: 
public static void sortiere (int[]array){
	array = new int []{}; 
	int min = Integer.MIN_VALUE;
	for (int i=0;i<array.length;i++)
		min =array[0];
		for (int j=0;j<array.length-1;j++)
			min = array[j+1];

	

}
public static void main (String []args){
	 int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 }; 
	System.out.println(sortiere(test));
	
}
}

jetzt müsste das Programm doch eigentlich in der ersten for schleife das kleinste element suchen und an die erste stelle setzen, dann in der zweiten müsste er wieder das kleinste suchen und an die j+1 stelle setzen oder ?

oder hab ich da was übersehen? muss bei der 2. for-schleife eventuell noch genauer angeben dass er nicht nur eins wegstreichen soll, sondern genau das erste damit er das nicht nochmal ausgibt ? und wieso funktioniert das mit dem test in der main-methode nicht ?
 
du nimmst das übergebene array und überschreibst es erstmal mit einem neuem leeren array und gehst dann mit 2 for-schleifen (oder besser: gehst du nicht, da length==0) durch das neue leere array und ersetzt min mit array[0] und array[1]. das ergibt alles keinen sinn

eine methode die nichts, also void zurück gibt kann man nicht als string mit syso ausgeben


wenn du erstmal nur das kleinste element finden möchtest, empfehle ich dir zuerst mal irgend einen kleiner als vergleich einzubauen. eine gute referenz zum anfangen ist Integer.MAX_VALUE
 
Zuletzt bearbeitet von einem Moderator:
ok jetzt hab ich das mit dem leeren Array shcon mal gecheckt

Java: 
public static void sortiere (int[]array){
	
	for (int i=0;i<array.length;i++)
	System.out.print("unsortiert"+array[i]);
	
	int min = Integer.MIN_VALUE;  

	for (int i=0;i<array.length;i++)
		min =array[0];
		for (int j=0;j<array.length-1;j++)
			min = array[j+1];
		System.out.println("");
for (int i=0;i<array.length;i++)
	System.out.print("sortiert"+array[i]);

}
public static void main (String []args){
	 int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 }; 
	sortiere(test);
	
}

gut, jetzt sortiert er aber in der Tat nicht obwohl ich doch 2 For-Schleifen drin hab und dieses coole min, wieso macht er das nicht ? und wie war das mit dem Vergleichen gemeint?
 
naja beim sortieren muss man irgendwo überprüfen ob eine zahl kleiner ist als die anderen zahlen im array. kein vergleich, keine sortierung

[c]if (array < min) {tue was}[/c]
 
Also Leute ich bin am Ende, ich krieg das nicht hin ich habs jetzt in 3 Methoden aufgeteilt trotzdem hab ich keine Ahnung wie er das machen soll dass er das sotiert
Java: 
	public static void kleinste (int[]array){
	int min = Integer.MAX_VALUE;	
		for (int i=0; i<array.length; i++)
			if (array[i]<min){
				min=array[i];
				
			}
	}
	public static void sortiere (int []array){
		
	}
		public static void main (String []args){
		 int[] test ={ 4, 2, 8, 5,9, 1,3,6,0,7 }; 
		sortiere(test);
		
	}
}

Ist das irgendwas richtig? Ist die Methode kleinste richtig ?
 
BaxterStockman hat gesagt.:
Ist das irgendwas richtig? Ist die Methode kleinste richtig ?
Zum Vergrößern anklicken....

Nein, alleine schon das die Methode keinen Rückgabewert (void) hat ist falsch. du willst der Methode ja einen Array geben und sie soll dir die Position des kleinsten Elements zurückgeben:
Java: 
    public static int kleinste (int[]array){
        int minPosition = 0;
        int min = Integer.MAX_VALUE;    
        for (int i=0; i<array.length; i++)
            if (array[i]<min){
                min=array[i];
                
            }
        return minPosition; 
    }

Jetzt konzentrier dich ertsmal drauf das die diese Methode die Position des kleinsten Wertes zurückgibt.
 
Java: 
    public static void main(String [] args) {
        int[] zahlen = {4,3,2,1,5,8,9};
        System.out.println(kleinste(zahlen));
    }

    public static int kleinste (int[]array){
        int min = Integer.MAX_VALUE;

        for (int i=0; i<array.length; i++) {

            if (array[i]<min){
                min=array[i];
            }
        }

        return min;
    }

mit int statt void und einem return bekomsmt du dann auch den wert zurück und kannst ihn dir ausgeben. an sich aber richtig
 
ok danke, aber ich komm trotzdem nicht drauf, wie das gehen soll, dass er jetzt dann die 2. Zahl nimmt und weiter sortiert, bzw. die nächst größere Zahl.

ich hab ne methode sortiere geschrieben und wollte die methode kleinste per for schleife durchlaufen lasen aber das geht auch nicht irgendwie geht gar nichts
 
wie wäre es mit:
-nach dem kleinsten suchen
-das kleinste in ein neues array speichern und im alten löschen
schleif rumwickeln und so oft machen wie das array lang ist, dann das fertige array ausgeben
 
Der Algo geht doch eigentlich so:

for(i:0 ... n)
kleinstesElement = i;
for(j:i...n)
wenn element[j] kleiner als element[kleinstesElement]: keinstesElement = j;

swappe: kleinstesElement mit i

EDIT:
Nachzulesen in
The Art of Computer Programming Volume 3. s 139ff (Kunth)
und
in Sedgewick aktuellem Kurs:
COS 226, Spring 2010: Lectures
(4)
 
Zuletzt bearbeitet:
Java: 
	public static void main(String [] args) {
        int[] zahlen = {0,1,4,3,2,5,8,9};
        System.out.println(kleinste(zahlen));
    }
 
    public static int kleinste (int[]array){
        int min = Integer.MAX_VALUE;
 
        for (int i=0; i<array.length; i++) {
 
            if (array[i]<min){
                min=array[i];
                            }
           for (int j=i+1;j<array.length-1;j++)
        	   if (array[i]<min)
        		   min=array[i+1];
        }
 
        return min;
    }

jetzt hab ich ne zweite for schleife in die erste eingebaut und einfach alles +1 gemacht, aber ne wirkung hat es trotzdem nicht ? wie beschrieben hat es mit der 2. Methode nicht funktioniert, aber wieso funktioniert das mit der 2. For-Schleife nicht ? merkt er sich das i nicht ? bzw. wie kann ihc das machen dass er sich das merkt ?
 
Die zweite schleife ergibt einfach keinen sinn, mal dir doch mal auf papier auf was da passiert und füge in jede schleife bei "min =" ein system.out.println(min); ein und schau was du eigentlich machst

die kleinste methode war in ordnung so wie sie war, du brauchst noch eine sortier methode mit ner schleife
 
Meinen Nerven zu liebe - ich halte es wirklich nicht mehr aus!

Java: 
	public static int groesste (int[]array){
		int max = Integer.MIN_VALUE;

		for (int i=0; i<array.length; i++) {
			if (array[i]>max){
				max=array[i];
			}
		}
		return max;
	}

und wenn du es jetzt nicht schaffst - ja ich weiss ich bin wieder mal böse - Guck mal
 
😛
Java: 
    public static int groesste (int[] array){
        int max = Integer.MIN_VALUE;
        for (int k : array) 
            max = java.lang.Math.max(k, max);
        return max;
    }
 
...wobei mich das grösste keinste Gedusel immer noch irgendwie komisch tönt für einen SelectionSort.
Oder wie soll der Algo dann ablaufen? Mach ein neues Array ( +O(N) Space). Finde Grössten. Setzt in ans Ende des Arrays und entferne ihn vom originalen Array (= Arraycopy oder was?) und mach das nochmals?
 
Der Müde Joe hat gesagt.:
...wobei mich das grösste keinste Gedusel immer noch irgendwie komisch tönt für einen SelectionSort.
Oder wie soll der Algo dann ablaufen? Mach ein neues Array ( +O(N) Space). Finde Grössten. Setzt in ans Ende des Arrays und entferne ihn vom originalen Array (= Arraycopy oder was?) und mach das nochmals?
Zum Vergrößern anklicken....

naja das ist eine möglichkeit zu sortieren oder?

ich habe 10 zahlen vor mir, nehm die kleinste weg und packe sie an den anfang meiner neuen reihe, dann guck ich die zahlen wieder an und nehm wieder die kleinste weg und leg sie neben zahl1 usw bis alle zahlen sortiert in meiner neuen reihe liegen
 
>naja das ist eine möglichkeit zu sortieren oder?

Wenn auch eine sehr Ineffiziente. (mal ausser betrach gelassen, dass Selection sowieso lahm ist)

>ich habe 10 zahlen vor mir, nehm die kleinste weg und packe sie an den anfang meiner neuen reihe,

Wieso noch gleich 'in-place'. Such das kleinste, vertausche es mit der ersten Stelle. Mach das gleiche einfach
nicht mehr über das ganze Array sondern lass die erste Stelle weg (Subarray von i...n und swap nach i).
 
Der Müde Joe hat gesagt.:
...wobei mich das grösste keinste Gedusel immer noch irgendwie komisch tönt für einen SelectionSort.
Zum Vergrößern anklicken....

Ne, das macht auch keinen Sinn. Es geht nicht darum das kleinste Element zurück zu geben, sondern den Index des kleinsten Elements im Array. (Auch wenn man mit dem kleinsten Element natürlich in einer weiteren Schleife den Index bestimmen könnte 😉)

Auch wenn ich mich jetzt wieder unbeliebt mache*
Java: 
import java.util.Arrays;

public class Aufgabe {
	public static void main(String[] args) {
		
		int[] array = new int[]{1,9,10,3,88,2,6,32,0,4};
		selectionSort(array);
		System.out.println(Arrays.toString(array));
	}
	
	public static int getMinElemIndex(int[] array, int index){
		int minElemIndex = index;
        for (int idx=index+1; idx<array.length; idx++) {
            if (array[minElemIndex] > array[idx]) {
            	minElemIndex = idx;
            }
        }
        return minElemIndex;
	}
	
	public static void selectionSort(int[] array) {
	    for (int idx=0; idx<array.length-1; idx++) {
	        int minElemIndex = getMinElemIndex(array,idx);
	        if (minElemIndex != idx) { 
	            int temp = array[idx];
	            array[idx] = array[minElemIndex];
	            array[minElemIndex] = temp;
	        }
	    }
	}

}

* allerdings würde er da auch drauf kommen wenn er einmal nach "Selection sort java" googlen würde, in den ersten 3 Treffern, z.B. Java: Selection Sort
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Selection Sort funktioniert nicht.
Antworten: 3
Selection Sort in Liste implementieren
Antworten: 3
Selection-Sort // Array *help*
Antworten: 2
Selection-Sort-Algorithmus
Antworten: 9
Selection Sort schnellere Variante
Antworten: 17

Zurück
Oben