Straight selection sort

Van Wikipedia

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.

[bewerk] Voorbeeld

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;
    }
  }
}