Posts Tagged ‘select sort’

Selection Sort

maj 21, 2010

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

Annonser