Selection sort

Selection sort is a sort algorithm that works as follows:

remove the lowest datum one at a time until the set of data is empty

The naive algorithm, iterating through a list of n unsorted items, has a worst-case, average-case and best-case run-time of O(n²), assuming that comparisons can be done in constant time.

Heapsort optimizes the algorithm by using a heap data structure to speed up the finding and removing of the lowest datum.

Example

Here is a simple implementation of selection sort in C (from pd lecture notes (http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture1.html)):

int find_min_index (float [], int, int);
void swap (float [], int, int);
 
/* selection sort on array v of n floats */
 
void selection_sort (float v[], int n) {
  int  i;
 
  /* for i from 0 to n-1, swap v[i] with the minimum
   * of the i'th to the n'th array elements
   */
  for (i=0; i<n-1; i++) 
    swap (v, i, find_min_index (v, i, n));
} 
 
/* find the index of the minimum element of float array v from
 * indices start to end
 */
int find_min_index (float v[], int start, int end) {
  int  i, mini;
 
  mini = start;
  for (i=start+1; i<end; i++) 
    if (v[i] < v[mini]) mini = i;
  return mini;
}
 
/* swap i'th with j'th elements of float array v */
void swap (float v[], int i, int j) {
  float	t;
 
  t = v[i];
  v[i] = v[j];
  v[j] = t;
}