|
One advantage of the Selection Sort is that there are very few record
swaps. Unlike some other sorting algorithms, like insertion sort, for
example, the Selection sort swaps elements only when it knows it is
swapping one of them into the correct position in the final data set.
In total a maximum of n-1 data movement operations must be performed
by this algorithm.
For this reason if you are dealing with a situation where it is
``expensive'' to exchange data items, this sort might be the best
solution. Another, possibly better, way to sort ``expensive to move''
records is to keep a pointer to each record's key and simply sort the
pointers. This is akin to labeling all the boxes in your warehouse
with cards that give their location and then sorting the cards rather
than getting out a forklift and sorting the boxes.
This is a relatively expensive algorithm in terms of data comparison
operations. It always will cost n-1 comparisons to find the maximum
item in a set. Since the maximum must be found n times, the overall
number of comparisons needed by the Selection Sort is quadratic, order
n2 to be exact.
This sort is essentially a modified Bubble Sort which does not
continually swap adjacent elements but, rather, remembers where to put
elements once they are selected. Although Selection Sort is more
efficient than the Bubble Sort by a constant factor in most
situations, there is usually a better way to sort data than to
choose a selection sort.
| 
Search