| << 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.
Notification Switch
Would you like to follow the 'My first collection' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|