| << Chapter < Page | Chapter >> Page > |
Above the methods are defined as following:
final void sort(Object [] A, int lo, int hi) -- sorts the given unsorted array of objects,
A , defined from index
lo to index
hi , inclusive. This method is implemented here and marked
final to enforce its invariance with respect to the subclasses. It is this method that implements Merritt's split-sort-join process.
abstract int split(Object [] A, int lo, int hi) -- splits the given unsorted array of objects,
A , defined from index
lo to index
hi , inclusive, into two adjacent sub-arrays. The returned index is the index of the first element of the upper sub-array. The implementation of this abstract method is in the sub-classes.
abstract void join(Object [] A, int lo, int s, int hi) -- joins two sorted adjacent sub-arrays of objects in the array
A , where the lower sub-array is from index
lo to index
s , inclusive, and the upper sub-array is from index
s to index
hi , inclusive. The implementation of this abstract method is in the subclasses.
Here's the full code for the abstract
ASorter class, the abstract superclass for all concrete sorters and the implementation of Merritt's template for sorting:
Note:
Asorter class
package sorter;
public abstract class ASorter{
protected AOrder aOrder;/**
* The constructor for this class.* @param aOrder The abstract ordering strategy to be used by any subclass.
*/protected ASorter(AOrder aOrder)
{this.aOrder = aOrder;
}/**
* Sorts by doing a split-sort-sort-join. Splits the original array into two subarrays,* recursively sorts the split subarrays, then re-joins the sorted subarrays together.
* This is the template method. It calls the abstract methods split and join to do* the work. All comparison-based sorting algorithms are concrete subclasses with
* specific split and join methods.* @param A the array A[lo:hi] to be sorted.* @param lo the low index of A.
* @param hi the high index of A.*/
public final void sort(Object[]A, int lo, int hi)
{if (lo<hi)
{int s = split (A, lo, hi);
sort (A, lo, s-1);sort (A, s, hi);
join (A, lo, s, hi);}
}/**
* Splits A[lo:hi]into A[lo:s-1] and A[s:hi]where s is the returned value of this function.
* @param A the array A[lo:hi]to be sorted.
* @param lo the low index of A.* @param hi the high index of A.
*/protected abstract int split(Object[] A, int lo, int hi);/**
* Joins sorted A[lo:s-1]and sorted A[s:hi] into A[lo:hi].
* @param A A[lo:s-1]and A[s:hi] are sorted.* @param lo the low index of A.
* @param hi the high index of A.*/
protected abstract void join(Object[]A, int lo, int s, int hi);
/*** An accessor method for the abstract ordering strategy.
* @param aOrder*/
public void setOrder(AOrder aOrder){
this.aOrder = aOrder;}
}AOrder is an abstract ordering operator whose concrete implementations define the binary ordering for the object being sorted. The examples below, only use the
AOrder.lt(Object x, Object y) method, which returns
true if
x<y . The sorting framework could easily be modified to use
java.util.Comparator instead with no loss of generality.
Notification Switch
Would you like to follow the 'Design patterns' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|