Selection Sort schnellere Variante

[updater]

Hey Leute,

Ich will die Selection Sort suche schneller machen, das heißt die Variante soll das Minimum und Maximum gleichzeitig bestimmen und dann mit dem Element ,dass am weitesten links bzw am weitesten rechts steht,vertauscht werden. D.h. die Restfolge wird von beiden Seiten her kleiner.

Bisher habe ich nur eine Variante , die nur das Maximum sucht und mit dem am weitesten rechts vertauscht wird.

Mein bisheriger Code:

public class Sort {

	static void swap (int [] array, int index1, int index2)

	{
	int tmp = array[index1];
	array[index1] = array[index2];
	array[index2] = tmp;
	}
	
	
	static void SelectionSort (int [] array) {
		int mark = array.length - 1;
		while (mark > 0) {
		
		int max = 0; 
		for (int i = 1; i <= mark; i++) 
		if (array [i] > array [max]) 
		max = i;
		swap (array, mark, max);
		
		mark--;
		}
		}
	public static void main(String[] args) {
		
		int [] F = new int[20];
		
		for (int i = 0; i<F.length; i++)
		{
			int key= (int) Math.floor(Math.random()*F.length);
			F[i] = key;}
		SelectionSort(F);
		int a=0;
		while (a<F.length){
			print(F[a] + ", ");
			a++;
		}
	}

}

Wie könnte ich das am besten umschreiben? Ich bin noch Neuling und habe es schon selbst versucht aber leider ohne Erfolg. Bei Google habe ich auch nichts passendes gefunden. Irgendwelche Ideen, Tipps oder sogar eine Lösung?

Danke schonmal im Vorraus

mfg

updater

 

[Andi_CH]

Du umschreibst es ja schon!

dort wo du das Maximum suchst baust du zusätzlich noch den Code ein, der auch das Miniumum sucht
dort wo du das Maximum verschiebst baust du zusätzlich noch den Code ein der das Minimum verschiebt

Mit dem Vorlagen von Maximum suchen und Maximum verschieben ist sicher möglich nach kurzem Nachdenken zu lösen.

Lösung? Hm - lieber nicht, dann hättest du ja nichts gelernt

 

[updater]

Hey,

Erstmal Danke für deine schnelle Antwort

Ich habe es jetzt mal so umgeschrieben

static void SelectionSort (int [] array) {
		int marker = array.length - 1;
		while (marker > 0) {
		
		int max = 0; 
		int min = 0;
		
		for (int i = 1; i <= marker; i++) {
		if (array [i] > array [max]) 
		max = i;
		swap (array, marker, max);}
		
		for (int i = 1; i <= marker; i++) {
			if (array [i] < array [min]) 
			min = i;
			swap (array, marker, min);}
		
		marker--;
		}
		}

Nun gibt er mir aber das sortierte array rückwärts aus .
Bsp: 19, 19, 18, 18, 16, 15, 15, 15, 13, 9, 8, 6, 5, 4, 4, 3, 2, 1, 1, 0,

 

[Andi_CH]

Uff - grober Fehler - Eine Methode darf nicht gleich heissen wie die Klasse - ausser sie ist ein Konstruktor --- betreffend umdrehen melde ich mich gleich

Sag doch einfach "sort" oder "doIt" oder sowas anstatt static void sort ....

Hm - was ist print?

Auch schon was von "for" loops gehört? ;-)

 

[Andi_CH]

EDIT Käse geschrieben !

 

[updater]

Uff - grober Fehler - Eine Methode darf nicht gleich heissen wie die Klasse - ausser sie ist ein Konstruktor --- betreffend umdrehen melde ich mich gleich

Sag doch einfach "sort" oder "doIt" oder sowas anstatt static void sort ....

Hm - was ist print?

Auch schon was von "for" loops gehört? ;-)

Klasse heißt bei mir anders, hab sie hier nur umbenannt, sonst würde ich das Programm garnicht starten können, da der Compiler meckern würde.
"print" macht das selbe wie System.out.print();, aber das ist auch nebensächlich, das funktioniert schon.

 

[Andi_CH]

Ich schnall das Verfahren nicht - sorry.
Quick and dirty Lösung ist den Array in umgekehrter Richtung auszugeben

Wie kommst du mit nur einem Marker über die Runde?

 

[updater]

Ich schnall das Verfahren nicht - sorry.
Quick and dirty Lösung ist den Array in umgekehrter Richtung auszugeben

Hey,

Habs jetzt mal so gemacht,dass ich das Array rückwärts ausgebe.

Vielleicht hat noch jemand eine andere Idee. Danke für deine Hilfe bisher

 

[Andi_CH]

Ich gebs auf!
mir scheint es so, dass es reiner Zufall ist dass es funktioniert
- loops starten bei 1 statt 0

Wenn du zufrieden mit der quick and dirty Lösung bist, ok

 

[updater]

Ich gebs auf!
mir scheint es so, dass es reiner Zufall ist dass es funktioniert
- loops starten bei 1 statt 0

Wenn du zufrieden mit der quick and dirty Lösung bist, ok

Da muss irgendwo ein Denkfehler im Programmiercode sein. Ich glaube das Programm macht das nicht gleichzeitig sondern erst mit Maximum, dann mit Minimum. Kann jemand anderes helfen ???:L

Danke

 

[Andi_CH]

Ich versuche noch immer das anfangsprogramm zu verstehen.

Also das mit start bei 1 ist ok, aber du kannst schon bei maxMarker - 1 abbrechen sonst tauscht der am Schluss noch n gegen n.

Das mit den Minima kannst du sicher nicht mit maxMarker lösen sondern musst einen min Marker bestimmen.

Die Frage ist einfach ob du dabei wirklich etwas gewinnst?

 

[Andi_CH]

und den Abbruch könntest du auch noch optimieren

Schau mal!

4, 2, 3, 1, 
swap 3, 0
1, 2, 3, 4,  <- hier könnte man abbrechen! 
swap 2, 1
1, 3, 2, 4, 
swap 1, 0
3, 1, 2, 4, 
3, 1, 2, 4,

 

[updater]

Ich versuche noch immer das anfangsprogramm zu verstehen.

Also das mit start bei 1 ist ok, aber du kannst schon bei maxMarker - 1 abbrechen sonst tauscht der am Schluss noch n gegen n.

Das mit den Minima kannst du sicher nicht mit maxMarker lösen sondern musst einen min Marker bestimmen.

Die Frage ist einfach ob du dabei wirklich etwas gewinnst?

Ja, es müsste schneller gehen ,da in einem Durchlauf sowohl der kleinste als auch der größte Wert ermittelt wird und dann mit dem am weitesten links bzw. am weitesten rechts stehenden Element vertauscht wird. Dadurch wird die zu betrachtende Restfolge von beiden Seiten her kleiner.

EDIT:

Ja optimieren könnt ich es noch, aber erst wenn der Code stimmt. Ich versuchs mal weiter :bahnhof:

 

[updater]

hat noch jemand einen Vorschlag? Komme nicht weiter ???:L

Danke!

 

[Landei]

Vorschlag: Schreibe dir erst mal einen Test. Sonst bist du nie sicher, ob es richtig läuft.

Ich versuche mal aus'm Kopp (JUnit wäre besser, aber kann man ja noch ummodeln):

import java.util.*;
class SortTest {

   private static Random random = new Random();
   public static void test() {
       for(int anzahlTests = 0; anzahlTests < 100; anzahlTests++) {
           int len = 3 + random.nextInt(10); 
           int[] selectionSortArray = new int[len];
           int[] javaSortedArray = new int[len];
           for(int i = 0; len; i++) {
               int r = random.nextInt(20);
               selectionSortArray[i] = r;
               javaSortedArray[i] = r;
           } 
           DeineKlasse.selectionSort(selectionSortArray);
           Arrays.sort(javaSortedArray);
           if(! Arrays.equals(selectionSortArray,javaSortedArray)) {
               System.err.println("WTF? " + Arrays.toString(selectionSortArray));
           }
       }
   }
}

 

[Andi_CH]

Ja, es müsste schneller gehen ,da in einem Durchlauf sowohl der kleinste als auch der größte Wert ermittelt wird und dann mit dem am weitesten links bzw. am weitesten rechts stehenden Element vertauscht wird. Dadurch wird die zu betrachtende Restfolge von beiden Seiten her kleiner.

EDIT:

Ja optimieren könnt ich es noch, aber erst wenn der Code stimmt. Ich versuchs mal weiter :bahnhof:

Ich würde erst einmal den Originalcode mit nur einer Vertauschung optimieren und der läuft ja mehr oder weniger - allerdings ist es schon seltsam, dass fröhlich weitervertauscht wrid, obwohl der Array ja im obigen Beispiel nach dem ersten Vertauschen sortiert ist....

... und dann auf Papier aufzeichnen was wann wie vertauscht werden muss

Alles in allem ist das kein Java-Problem und es ist fraglich in wie weit das hier das richtig Forum ist.

 

[updater]

Ich würde erst einmal den Originalcode mit nur einer Vertauschung optimieren und der läuft ja mehr oder weniger - allerdings ist es schon seltsam, dass fröhlich weitervertauscht wrid, obwohl der Array ja im obigen Beispiel nach dem ersten Vertauschen sortiert ist....

... und dann auf Papier aufzeichnen was wann wie vertauscht werden muss

Alles in allem ist das kein Java-Problem und es ist fraglich in wie weit das hier das richtig Forum ist.

Erstmal danke für eure Hilfe! Ich denke du hast recht ,dass das kein Java Problem ist, deshalb werde ich den Thread schließen. Falls ich die Lösung habe, werde ich sie noch posten.

mfg
updater

 

[Stapf_JAVA]

    public int[] sortieren(int[] folge){
        int rightbound = folge.length-1;
        int leftbound=0;
        int i; //Laufindex

        while(rightbound>leftbound){
            for(i=leftbound; i<rightbound; i++){ //Maximum suchen
                if(folge[i]>folge[i+1]){
                    folge = elementeTauschen(i, i+1, folge);//tauschen nach rechts
                }//END if
            }//END for
            for(i=rightbound; i>leftbound; i--){//Minimum suchen
                if(folge[i]<folge[i-1]){
                    folge = elementeTauschen(i-1, i, folge);//tauschen nach links
                }//END if
            }//END for
            rightbound--;
            leftbound++;
        }//END while

        return folge;

    }//END sortieren





    public int[] elementeTauschen(int index,int index2, int[] folge){
        int tmp = 0;
        tmp = folge[index2];
        folge[index2] = folge [index];
        folge[index] = tmp;

        return folge;


    }//END elementeTauschen