Lecture
In selection sort, the element with the smallest value is chosen from the array and swapped with the first element. Then, from the remaining n - 1 elements, the element with the smallest key is again chosen and swapped with the second element, and so on. These swaps continue up to the last two elements. For example, if the selection method is applied to the array dcab, each pass will look as shown below:
Start d c a b Pass 1 a c d b Pass 2 a b d c Pass 3 a b c d
The following code demonstrates the simplest form of selection sort:
/* Selection sort. */
void select(char *items, int count)
{
register int a, b, c;
int exchange;
char t;
for(a=0; a < count-1; ++a) {
exchange = 0;
c = a;
t = items[a];
for(b=a+1; b < count; ++b) {
if(items[b] < t) {
c = b;
t = items[b];
exchange = 1;
}
}
if(exchange) {
items[c] = items[a];
items[a] = t;
}
}
}
Unfortunately, just as in bubble sort, the outer loop executes n - 1 times, while the inner loop executes, on average, n/2 times. Consequently, selection sort requires
1/2(n2-n)
comparisons. Thus, this is an algorithm of order n2, which is why it is considered too slow for sorting a large number of elements. Although the number of comparisons in bubble sort and selection sort is the same, in the latter the average number of exchanges is much smaller than in bubble sort.
Also called sort by selection and selection sampling sort.
Comments