Selection sort (original) (raw)
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_2), 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):
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="" n));="" <="" pre="">} / 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;="" pre="">} /* 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;
} </end;>
</n-1;>