Der Selectionssort Algorithmus ist der naive Ansatz, der uns beim Sortieren wohl als erstes einfallen würde, da er ziemlich genau dem entspricht wie wir normalerweise Dinge sortieren würden. Nehmen wir als Beispiel einmal ein Paar Spielkarten mit aufgedruckten Zahlen. Wenn wir diese nun nach der Größe sortieren sollen, werden wir uns zuerst die kleinste Karte aus den unsortierten Karten herausnehmen und auf einen neuen (den sortierten) Stapel legen. Danach nehmen wir aus den verbleibenden unsortierten Karten wieder die kleinste Karte heraus und legen sie auf den sortierten Stapel. Das wiederholen wir solange bis es keine unsortierten Karten mehr gibt und alle Karten sortiert auf einem Stapel liegen. Wenn wir so vorgehen, dann nennt man dieses Verfahren auch Minsort ¹⁾. Genauso gut können wir auch mit der größten Karte beginnend immer die größte Karte wählen, was dann Maxsort ²⁾ genannt wird.

Ein einfacher Ansatz von Minsort in C könnte in etwa so ausschauen:

/// @param values Zeiger auf zu sortierendes Array
/// @param len Länge des Arrays
void selectionSort( int* values, size_t len )
{
  // Alle Elemente durchlaufen (Das letzte können wir auslassen,
  // da jedes Element sowieso mit seinem Nachfolger verglichen wird)
  for( size_t start = 0; start < len - 1; ++start )
  {
    // Index für aktuell kleinstes Element (Am Anfang das erste Element wählen)
    size_t min_index = start;
 
    // Alle auf das aktuelle Element folgenden Elemente durchlaufen
    for( size_t cur = start + 1; cur < len; ++cur )
    {
      // Mit dem aktuellen Minimum vergleichen
      if( values[cur] < values[min_index] )
        min_index = cur; // Neues Minimum an der Stelle 'cur' gefunden
    }
 
    // Testen ob ein neues Minimum gefunden wurde
    if( min_index != start )
    {
      // Elemente vertauschen
      int temp = values[start];
      values[start] = values[min_index];
      values[min_index] = temp;
    }
  }
}

In C++ können wir mit Hilfe der STL und von Templates einen universellen Selectionsort Algorithmus mit nur kleinen Anpassungen der C-Implementierung wie folgt schreiben:

/// @param values Zeiger auf zu sortierendes Array
/// @param len Länge des Arrays
template<typename T>
void selectionSort( T* values, size_t len )
{
  // Alle Elemente durchlaufen (Das letzte können wir auslassen,
  // da jedes Element sowieso mit seinem Nachfolger verglichen wird)
  for( size_t start = 0; start < len - 1; ++start )
  {
    // Index für aktuell kleinstes Element (Am Anfang das erste Element wählen)
    size_t min_index = start;
 
    // Alle auf das aktuelle Element folgenden Elemente durchlaufen
    for( size_t cur = start + 1; cur < len; ++cur )
    {
      // Mit dem aktuellen Minimum vergleichen
      if( values[cur] < values[min_index] )
        min_index = cur; // Neues Minimum an der Stelle 'cur' gefunden
    }
 
    // Testen ob ein neues Minimum gefunden wurde
    if( min_index != start )
    {
      // Elemente vertauschen
      std::swap( values[start], values[min_index] );
    }
  }
}

schreiben