Selection Sort

The Reinvigorated Programmer utfärdade en ny utmaning, implementera selection sort. Selection Sort är en ganska enkel (läs ineffektiv) sorteringsrutin som letar igenom en uppsättning värden och väljer ut det lägsta och placerar det först i en lista (kan vara in-place, dvs samma lista som innehåller de osorterade värdena).

Jag tyckte det här var en bra övning att träna på lite mer formella algoritm-beskrivningar så jag började med att sätta upp invarians, gränsfunktioner och pre/post-conditions (hur översätts dessa?) och skrev sedan min algoritm utifrån dessa beskrivningar. Eftersom det är första gången jag skriver dessa formella beskrivningar är jag lite osäker på om jag uttrycker det jag vill att algoritmen skall göra på rätt sätt. Jag uppskattar därför alla kommentarer på nedanstående c-kod och beskrivningar.

/*
 * Invariant: if val at any position i in an array array of length len
 *  is lower than the current value at j in the array the value is at
 *  an i > j and i < len
 *
 * bound function: 0 <= j < length - 1
 *                 j <  i < length
 *
 * precondition:  a[] is an unsorted array of integers of the size len
 * postcondition: a[] is an array sorted higher to lower
 * */
void selectSort(int a[], int len)
{
  int tempStore, i, j;

  for (j = 0; j < len - 1; j++)
  {
    for (i = j + 1; i < len; i++)
    {
      if (a[i] < a[j])
      {
	tempStore = a[j];
	a[j] = a[i];
	a[i] = tempStore;
      }
    }
  }
  return;
}

syntax highlighted by Code2HTML, v. 0.9.1

Etiketter: , ,

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s


%d bloggare gillar detta: