Selection Sort Algorithmus

[schlafmütze]

Code: Alles auswählen

void Numsort (double v[], int len)
{
  for( int i = 0;  i  <  len -1;  i++)
   {
      int mini = i;

     for( int j = i + 1;  j < len; j++)
         if( v[j] < v[mini] )
          mini = j;

    double temp = v[i];
                 v[i] = v[mini];
                 v[mini] = temp;

    }   /* For schließen*/
    
} /*Funktion schließen*/

Ich versuche gerade das selection Sort Algorithmus zu verstehen.

Code: Alles auswählen

for( int i = 0;  i  <  len -1;  i++)
   {
      int mini = i;

Hier sucht er nach den kleinsten Element und gibt es an mini weiter.

Code: Alles auswählen

for( int j = i + 1;  j < len; j++)
         if( v[j] < v[mini] )
          mini = j;

Hier wird i um eins erhöht und j weitergegeben folgend wird j im inkrementiert und muss nicht größer als len sein.
Jetzt wird j mit mini verglichen wenn j größer ist wird der Wert von j nach mini verschoben und somit ist mini um ein Element gewachsen.

Code: Alles auswählen

 double temp = v[i];
                 v[i] = v[mini];
                 v[mini] = temp;

Hier weiß ich nicht wozu tauschen der Elemente gut ist.
Ich habe mir das C Tutorial angeguckt allerdings ist das nichts von Selection Sort Algorithmus zu finden allerdings nur von Bubble und Quick Sortieralgorithmen
Korrigiert mich bitte was ich falsches verstanden habe und danke im voraus.

[Kerli]

Code: Alles auswählen

 double temp = v[i];
                 v[i] = v[mini];
                 v[mini] = temp;

Hier weiß ich nicht wozu tauschen der Elemente gut ist.

Du hast ja an der Stelle 'mini' den kleinsten, unsortierten Wert. Deshalb musst du den auch an die aktuelle Stelle 'i' schreiben. Falls zufälligerweise eh an der Stelle 'i' der kleinste Wert ist passiert nichts, da dann i == mini.

Ich habe mir das C Tutorial angeguckt allerdings ist das nichts von Selection Sort Algorithmus zu finden allerdings nur von Bubble und Quick Sortieralgorithmen

Ich hab zumindest einmal die Überschrift hinzugefügt. Vielleicht komm ich heute oder morgen noch dazu etwas zu schreiben Ansonsten ist auch der Artikel auf Wikipedia ganz gut...

[nufan]

Bei Selectsort musst du zwischen sortiertem und unsortiertem Bereich unterscheiden. Der sortierte Bereich hat einen Index < i, der unsoertierte >= i. Am Anfang gilt der Array als komplett unsortiert.

Code: Alles auswählen

for( int i = 0;  i  <  len -1;  i++)

Du gehst den ganzen Array exklusive das letzte Element durch. Wenn du nur noch ein einziges unsortiertes hast ist es nämlich automatisch das letzte bzw. höchstwertige.

Code: Alles auswählen

int mini = i;

i ist der Index des ersten unsortierten Elements. mini ist der Index des kleinsten im Durchlauf gefunden Wertes. Am Beginn sagst du einfach das erste unsortierte Element ist das Minimum.

Code: Alles auswählen

     for( int j = i + 1;  j < len; j++)
         if( v[j] < v[mini] )
           mini = j;

Jetzt gehst du durch den Rest des Arrays und suchst das Minimum. Findest du etwas kleineres als den Wert mit dem Index mini, wird es zum Minimum (Index wird mini zugewiesen).

Code: Alles auswählen

    double temp = v[i];
                 v[i] = v[mini];
                 v[mini] = temp;

Du vertauschst das erste unsortierte Element mit dem Minimum. Dadurch bekommst du eine aufsteigende Ordnung.
Beim nächsten Schleifendurchlauf gehört das eben vertauschte Element mit dem Index mini bereits zum sortierten Bereich. i wird erhöht und das ganze Spiel geht von vorne los.

Hier hab ich übrigens eine Seite mit guten Animationen zu verschiedenen Algorithmen gefunden:
http://www.cs.oswego.edu/~mohammad/clas ... rt2-E.html
Geh das mal langsam durch oder zeichne dir so etwas in der Art auf und geh den Code in Gedanken durch, das hilft oft.

[Kerli]

Ich habe mir das C Tutorial angeguckt allerdings ist das nichts von Selection Sort Algorithmus zu finden [...]

Jetzt schon

http://www.proggen.org/doku.php?id=c:selectionsort

Ist zwar noch nicht ganz fertig, aber das meiste sollte schon dabei sein...