Lektion 50:

straight selection sort

 Das nächste Sortierverfahren ist straight selection sort. Es funktioniert folgendermaßen:

  • Aus dem Array wird der kleinste Wert gesucht.
  • Dieser Wert wird mit dem ersten Array-Element vertauscht.
  • Aus dem Rest-Array wird der kleinste Wert gesucht.
  • Dieser Wert wird mit dem 2. Element vertauscht.
  • Aus dem Rest-Array wird der kleinste Wert gesucht.
  • Dieser Wert wird mit dem 3. Element vertauscht.
  • usw.

Das wird so lange gemacht, bis das Rest-Array nur noch ein Element hat.

void straightSelectionSort(int *array,int size)
{
   for(int arrayAnfang=0;arrayAnfang<size-1;++arrayAnfang)
   {// arrayAnfang läuft von 0 bis eins vor Ende des Arrays
      // Suchen des kleinsten Wertes
      int minPos=arrayAnfang;
      int minWert=array[arrayAnfang];
      for(int suchPos=arrayAnfang+1;suchPos<size;++suchPos)
      {
         if(array[suchPos]<array[minPos])
         {
            minPos=suchPos;
            minWert=array[suchPos];
         };
      };
      //Und austauschen
      swap(&array[arrayAnfang],&array[minPos]);
   };
};

Dieses Verfahren hat gegenüber bubble sort den Vorteil, daß deutlich weniger Vertauschungen durchgeführt werden müssen. Es bietet sich also an, wenn die zu sortierenden Werte nicht nur int-Werte sind, sondern größere Werte, die so viel Speicher beanspruchen, daß bereits das Vertauschen recht viel Zeit braucht. Es hat den Nachteil, daß sich keine so schönen Optimierungen wie in bubble sort anbieten.

Übung:

Nehmen Sie ca. 8 Spielkarten oder Münzen mit verschiedenen Werten und sortieren Sie diese nach dem oben angegebenen Verfahren. Legen Sie diese dazu nebeneinander auf einen Tisch und verwenden Sie für die Variablen arrayAnfang, minPos und suchPos entsprechend beschriftete Papierschnipsel, die Sie unterhalb der Münzen hin- und herschieben.



Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00