<< 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:

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;} } Note: 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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, My first collection. OpenStax CNX. Aug 03, 2009 Download for free at http://cnx.org/content/col10870/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'My first collection' conversation and receive update notifications?

Ask