Encyclopedia > Selection sort

  Article Content

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(n2), 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)):

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
East Hampton North, New York

... 14.5 km² (5.6 mi²) of it is land and none of the area is covered with water. Demographics As of the census of 2000, there are 3,587 people, 1,445 ...

 
 
 
This page was created in 22.8 ms