<< Chapter < Page Chapter >> Page >

The code to implement a selection sorter is straightforward. One need only implement the split and join methods where the split method always returns the lo+1 index because the smallest value in the (sub-)array has been moved to the index lo position. Because the bulk of the work is being done in the splitting method, selection sort is classified as an "hard split, easy join" sorting process.In the Java implementation of the SelectionSorter class below, the split method splits off the extrema (minimum, here) value from the sub-array, while the join method is a no-op.

Selectionsorter class

package sorter; /*** A concrete sorter that uses the Selection Sort technique. */public class SelectionSorter extends ASorter {/** * The constructor for this class.* @param iCompareOp The comparison strategy to use in the sorting. */public SelectionSorter(AOrder iCompareOp) {super(iCompareOp); }/** * Splits A[lo:hi]into A[lo:s-1] and A[s:hi]where s is the returned value of this function. * This method places the "smallest" value in the lo position and splits it off.* @param A the array A[lo:hi] to be sorted.* @param lo the low index of A. * @param hi the high index of A.* @return lo+1 always */protected int split(Object[] A, int lo, int hi){ int s = lo;int i = lo + 1; // Invariant: A[s]<= A[lo:i-1].// Scan A to find minimum: while (i<= hi) {if (aOrder.lt(A[i], A[s])) s = i;i++; // Invariant is maintained. } // On loop exit: i = hi + 1; also invariant still holds;// this makes A[s] the minimum of A[lo:hi]. // Swapping A[lo]with A[s]:Object temp = A[lo];A[lo] = A[s]; A[s]= temp; return lo + 1;} /*** Joins sorted A[lo:s-1] and sorted A[s:hi]into A[lo:hi].* This method does nothing. The sub-arrays are already in proper order. * @param A A[lo:s-1]and A[s:hi] are sorted.* @param lo the low index of A. * @param s* @param hi the high index of A. */protected void join(Object[] A, int lo, int s, int hi){ }}

What's interesting to note here is what is missing from the above code. A tradional selection sort aalgorithm is implemented using a nested double loop, one to find the smallest value and one to repeatedly process the ever-shrinking unsorted sub-array. Notice that the above code only has a single loop, which coresponds to the inner loop of a traditional implementation. The outer loop is embodied in the recursive nature of the sort template method in the ASorter superclass.

Notice also that the selection sorter implementation does not include any explicit connection between the split and join operations nor does it contain the actual sort method. These are all contained in the concrete sort method of the superclass. We describe the SelectionSorter class as a component in a framework (technically a "white box" framework, as described above). Frameworks display inverted control where the components provide services to the framework. The framework itself runs the algorithms, here the high level, templated sorting process, and call upon the services provided by the components to fill in the necessary processing pieces, e.g. the split and join procedures.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Principles of object-oriented programming. OpenStax CNX. May 10, 2013 Download for free at http://legacy.cnx.org/content/col10213/1.37
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?

Ask