Selection sort

[BaxterStockman]

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

int [] menge = new int []{4,6,1,9,3}

ne menge fest und will diese jetzt durch gehen und das kleinste Element suchen

 

[Painii]

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?

Nein, sowas musst du selber schreiben.

 

[maki]

ne menge fest und will diese jetzt durch gehen und das kleinste Element suchen

Selber schreiben, sollte 5 Zeilen nicht überschreiten, hat etwas mit Integer.MAX_VALUE zu tun

 

[Andi_CH]

Ja gibt es in meinem eigenen Code und sieht so aus:

	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 ;-)

 

[BaxterStockman]

ok also die for-schleife hab ich shcon mal

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?

 

[BaxterStockman]

so hab sie jetzt umgeschrieben

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 ?

 

[Gast2]

	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]

wenn ich das schreib, unterringelt er mir Arrays aus Arrays.toString mit "cannot be resolved" auch mich array.toString

 

[Michael...]

wenn ich das schreib, unterringelt er mir Arrays aus Arrays.toString mit "cannot be resolved" auch mich array.toString

Das ist zwar nicht Dein Problem aber:

import java.util.Arrays;

 

[Andi_CH]

so hab sie jetzt umgeschrieben

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 ?

Denk erst mal über Zeile 7 nach -
die Probleme der fehlenden Deklaration sind ja mit einem Mausklick gelöst

 

[BaxterStockman]

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 ?

 

[bone2]

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

 

[Andi_CH]

Du willst das Minimum suchen:

		for (int j=0;j<array.length-1;j++)
			min = array[j+1];

Falsch! Weisst du eigentlich was du willst? Ist einfach immer das nächste Element das Kleinste oder was?

 

[BaxterStockman]

ok jetzt hab ich das mit dem leeren Array shcon mal gecheckt

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?

 

[Gast2]

Trenn das doch erstmal auf...

Eine Methode die das kleinste Element in einem Array sucht, und eine die sortiert und die andere benutzt. So verhedderst du dich in den ganzen Schleifen.

Andy hat damit ja schon mal einen guten Vorschlage gemacht: http://www.java-forum.org/java-basics-anfaenger-themen/109670-selection-sort.html#post703418

 

[bone2]

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]

 

[BaxterStockman]

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

	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 ?

 

[Gast2]

Ist das irgendwas richtig? Ist die Methode kleinste richtig ?

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:

    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.

 

[bone2]

    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

 

[BaxterStockman]

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

 

[bone2]

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 Müde Joe]

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)

 

[Andi_CH]

Du suchst noch immer nicht das Minimum!!!!

Korriger das endlich erst mal!

 

[BaxterStockman]

	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 ?

 

[BaxterStockman]

scheiße hab die anderen Beiträge nicht gesehen, gut dann mach ich das mal

ps wieso such ich nicht nach dem minimum ? da kommt doch überall 0 raus wenn ichs kompilier

 

[bone2]

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

 

[Andi_CH]

Meinen Nerven zu liebe - ich halte es wirklich nicht mehr aus!

	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

 

[Landei]

    public static int groesste (int[] array){
        int max = Integer.MIN_VALUE;
        for (int k : array) 
            max = java.lang.Math.max(k, max);
        return max;
    }

 

[Der Müde Joe]

...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?

 

[Andi_CH]

    public static int groesste (int[] array){
        int max = Integer.MIN_VALUE;
        for (int k : array) 
            max = java.lang.Math.max(k, max);
        return max;
    }

Er schafft es, er schafft es nicht

 

[bone2]

...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?

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

 

[Der Müde Joe]

>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).

 

[bone2]

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).

is sicher der bessere weg, macht den anderen weg aber nicht falsch

 

[Gast2]

...wobei mich das grösste keinste Gedusel immer noch irgendwie komisch tönt für einen SelectionSort.

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*

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