Straight selection sort

Het sorteeralgoritme straight selection sort zoekt in een lijst steeds de kleinste om die te verwisselen met het element dat volgt op het vorige dat bovenaan de lijst werd geplaatst.

Deze misschien wat cryptische omschrijving laat zich het beste illustreren met een voorbeeld: de rij DCBA wordt eerst door verwisseling van het eerste element D en het kleinste element A ACBD, daarna door verwisselen van het tweede element C en het kleinste resterende element B ABCD, en daarna verandert er niets meer.

Het aantal benodigde vergelijkingen bij een rij van lengte n is (n-1) + (n-2) + … + 1. Het aantal benodigde verwisselingen is maximaal n-1.

Het onderstaand Java-codefragment sorteert de array asKey alfanumeriek op basis van Straight Selection:

for (int i= 0; i < asKey.length - 1; i++){
    String sMin= asKey[i]; // kleinste string (voorlopig)
    int iMin= i; // index van de kleinste string
    for (int j= i + 1; j < asKey.length; j++){
        if (asKey[j].compareTo(sMin) < 0){
            sMin= asKey[j];
            iMin= j;
        }
    }
    if (iMin != i){
        /* de kleinste string staat niet op plaats i maar verderop */
        asKey[iMin]= asKey[i];
        asKey[i]= sMin;
    }
}

Een voorbeeld in C ("invoer" is de te sorteren array, "lengte" is het aantal elementen in de array):

void straightselection(int invoer[],int lengte){
  int i,j,kleinste,tijdelijk;
  for(j=0;j<lengte-1;j++){
    kleinste=j;
    for(i=j+1;i<lengte;i++){
      if(invoer[i]<invoer[kleinste]) kleinste=i;
    }
    if(kleinste!=j){
      tijdelijk=invoer[j];
      invoer[j]=invoer[kleinste];
      invoer[kleinste]=tijdelijk;
    }
  }
}

In Python wordt dit:

def selectionsort(rij):
   for i in range(len(rij)):        
       min = i                      #Neem de eerste niet gesorteerde kaart als kleinste
       for j in range(i, len(rij)): #Overloop de rest van de niet-gesorteerde kaarten
           if rij[j]<rij[min]:
               min = j              #Is er een kleinere, zet dan zijn positie als minimum
       rij[i], rij[min] = rij[min], rij[i] #Verwissel de i-de kaart met de kleinste kaart