Selection-Sort-Algorithmus

[Tina87]

Hallo,
ich hab einen Algorithmus programmiert, der Zahlen sortieren soll nach dem selection-sort.
als erstes hätte ich gern gewusst, ob dieser wirklich dem prinzip des selection sort entspricht. bin mir da nicht so sicher. oder, ob es vielleicht was besseres gibt.
hatte nämlich mal in ner vorlesung ein programm gesehen mit "int pos" und "int min", kann mich aber nicht mehr genau erinnern.

und dann wollte ich, dass das programm nur einen bestimmten teil eines arrays sortiert, also von einem startpunkt bis zu einem endpunkt (einschließlich start und ende).
weiß aber irgendwie nicht wie ich das formulieren soll.

public class Test2 {
   public static void main(String[] args) {
       int [] daten = { 12, 4, 66, 34, 62, 2, 3, 7, 1, 678 };
       int start = daten[2];
       int end = daten[6];
       sortieren(daten, start, end);
   }
   
   public static void sortieren(int[] daten, int start, int end) {
      
      //SelectionSort-Algorithmus
      for(start = 0; start < daten.length; start++) {
         for(end = start; end < daten.length; end++) {
            if(daten[end] < daten[start]) {
               int temp = daten[end];
               daten[end] = daten[start];
               daten[start] = temp;
            }
         }
      }
      
      //das hier ist nur die Ausgabe des SelectionSort-Algorithmus
      for(start = 0; start < daten.length; start++) {
         System.out.print(daten[start]+ ",");
      }
   }
}

 

[eRaaaa]

Also wenn ich mir die Beschreibung bei Wikipedia anschaue, würde ich sagen (bitte korrigiert mich), dass das nicht ganz der Selectionsort ist Du tauschst öfters als eig. nötig und gewollt. Du müsstest in deiner 2. Schleifen, eig. immer nur das Minimum/Maximum ermitteln und dieses dann mit dem "aktuellen Index" tauschen.

Sei S der sortierte Teil des Arrays und U der unsortierte Teil. Am Anfang ist S noch leer, U entspricht dem ganzen Array. Das Sortieren durch Auswählen funktioniert so:

Suche das kleinste Element in U und vertausche es mit dem ersten Element.

Und noch was: Du übergibst der Methode ein start und ende- Integer...was hat das für einen Sinn, wenn du diese zu Beginn wieder auf 0 setzt?

 

[klein-odd]

Kannst Du das so anfangen, dass Du in der Menge von n- Zahlen (egal, ob integer oder double)
zwei Indizes start_index und end_index bestimmst ?

Damit teilst Du die Gesamtmenge von n - Elemensten in :

- Kopfteil (Elemente der Ursprungsmenge mit Indizes von 0 bis (start_index-1))
- Rumpf (Elemente der Ursprungsmenge mit Indizes von start_Index bis end_index) - der Rumpf soll doch sortiert werden,oder ?
- Schwanz (Elemente der Ursprungsmenge mit Indizes von (end_Index+1) bis n)

dann sortierst Du den Rumpf und klebst Du danch sozusagen alle drei Teile wieder zusammen
oder habe ich etwas übersehen ?

 

[Tina87]

also hab den selectionsort nochmal komplett neu gemacht, ohne jetzt an start und ende zu denken:

public class Test3
{
    public static void main (String [] args) {
        
        int [] daten = {2,7,3,9,1,5,7,4};
        sortieren(daten); 
        
    }
    
    static void sortieren (int [] daten) {
        
        for (int pos= 0; pos < daten.length-1; pos ++ ) {
            
            int min = pos;
            
            for (int i = pos+1; i < daten.length; i ++ ) {
                if (daten[i]<daten[min]) {
                    
                    min=i;
                }
            }
            
            int hilf=daten[pos];
            daten[pos]=daten[min];
            daten[min]=hilf;
        }
    }
}

1.) ist das jetzt besser so und auch richtig?
2.) wie gebe ich die zahlenfolge jetzt aus? system.out.println geht doch nicht so einfach,oder?
3.) das von "klein-odd" hab ich nicht verstanden...kann mir also nochmal jemand erklären, wie ich ein start und ein ende festlege, wo einschließlich den zahlen, dazwischen nur sortiert wird?

 

[eRaaaa]

1.) ist das jetzt besser so und auch richtig?
2.) wie gebe ich die zahlenfolge jetzt aus? system.out.println geht doch nicht so einfach,oder?
3.) das von "klein-odd" hab ich nicht verstanden...kann mir also nochmal jemand erklären, wie ich ein start und ein ende festlege, wo einschließlich den zahlen, dazwischen nur sortiert wird?

1.) Meiner Meinung nach schon! Ist okay so
2.) Wieso? Also was willst du? Willst du nach jedme Tauschvorgang dir das Array anschauen um zu sehen wie/was getauscht wurde? Dann schreib einfach eine for-/for-each Schleife nach daten[min] = hilf:

	    for (int i : daten) {
		System.out.print(i + " ");
	    }
	    System.out.println();

Wenn du nur das Endergebnis sehen willst, packs halt ganz ans Ende?
3.) eig. genauso, nur dass dein pos in der Schleife nicht bei 0 anfängt sondern bei start ;D und halt nicht bis daten.lenght, sondenr bis end

for (int pos = 0; pos < daten.length - 1; pos++) {

==>

for (int pos = start; pos < end-1; pos++) {

 

[Tina87]

Also...
Ja ich möchte nur am ende die zahlenfolge nochmal ausgeben.
mit deiner möglichkeit funktioniert es auch super.

Das mit dem einfügen von start und ende, hatte ich mir natürlich genau so gedacht, aber es funktioniert nicht. er gibt mir dann einfach die unsortierte komplette folge aus. oder ist noch was falsch?
nochmal zum drüberschauen:

public class Test3
{
    public static void main (String [] args) {
        
        int [] daten = {2,7,3,9,1,5,7,4};
        int start = daten [3];
        int end = daten [6];
        sortieren(daten, start, end);
        
        for (int i : daten) {
        System.out.print(i + " ");
        }
        System.out.println();
    }
    
    static void sortieren (int [] daten, int start, int end) {
        
        for (int pos= start; pos < end-1; pos ++ ) {
            
            int min = pos;
            
            for (int i = pos+1; i < end-1; i ++ ) {
                if (daten[i]<daten[min]) {
                    
                    min=i;
                }
            }
            
            int hilf=daten[pos];
            daten[pos]=daten[min];
            daten[min]=hilf;
        }
    }
}

 

[eRaaaa]

Mit

        int start = daten [3];
        int end = daten [6];

sagst du ihm
start = 9
ende = 7
:lol:

Was du vermutlich meinst ist einfach :

int start = 3;
int ende = 6;

p.s.: in deiner zweiten for-Schleife musst du doch aber bis < end laufen, nicht bis < end-1 ?!
Weil sonst tauschst du den letzten Platz ja unter Umständen garnicht !

 

[Tina87]

Ups, ja das war dumm.
aber bei start = 3
end = 6 kommt folgendes:
2 7 3 1 9 5 7 4
und das ist ja auch nicht gerade wirklich sortiert.

 

[eRaaaa]

Ups, ja das war dumm.
aber bei start = 3
end = 6 kommt folgendes:
2 7 3 1 9 5 7 4
und das ist ja auch nicht gerade wirklich sortiert.

Puh, jetzt komm ich selbst durcheinander...aber müsste eig. stimmen. Denn du sortierst ja nur die Zahlenfolge 9,1,5 der Rest bleibt ja bestehen
9,1,5 sortiert --> 1,5,9 + Rest vorne + Rest hinten --> 2,7,3,1,5,9,7,4

Ist jetzt Auslegungssache glaube ich wie man das implementiert (also ob ende inklusive oder exklusive sein soll )

 

[Tina87]

nee hat sich schon erledigt. das mit dem end-1 musste man zu end ändern, will ja inklusive end sortieren.
jetzt ist alles super!vielen lieben dank!