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 Marion, New York

... 2.79. In the town the population is spread out with 18.5% under the age of 18, 4.4% from 18 to 24, 20.6% from 25 to 44, 26.3% from 45 to 64, and 30.2% who are 65 years of ...

 
 
 
This page was created in 60.2 ms