next up previous contents index Search
Next: Source Code Up: 0.3.7 Selection Sort Previous: 0.3.7 Selection Sort Analysis

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.

Scott Gasch