Welcome back to the Sorting article.
For completeness, so you can copy and paste this sorting utility straight
in your own private back of tricks, here is the entire class:
-
public final class HeapSort {
-
-
private HeapSort() { } // no istances of this class possible
-
-
// given a Sortable, build a heap starting at node i. There a n nodes in total
-
private static void heapify(Sortable s, int p, int n) {
-
-
for (int r, l= (p<<1)+1; l < n; p= l, l= (p<<1)+1) {
-
-
// l is the maximum of l and r, the two subnodes of p
-
if ((r= l+1) < n && s.compare(l, r) < 0) l= r;
-
-
// check if parent p is less than maximum l
-
if (s.compare(p, l) < 0) s.swap(p, l);
-
else break;
-
}
-
-
// build a heap out of the Sortable in place
-
private static void phase1(Sortable s) {
-
-
// heapify all the non-leaf nodes
-
for (int n= s.length(), p= n/2; p >= 0; p--)
-
heapify(s, p, n);
-
}
-
-
// sort the Sortable
-
private static void phase2(Sortable s) {
-
-
for (int n= s.length(); --n > 0; ) {
-
s.swap(0, n); // put the root element in its place
-
heapify(s, 0, n); // and restore the heap again
-
}
-
}
-
-
// driver for the worked methods
-
public static Sortable sort(Sortable s) {
-
-
phase1(s); // build initial heap
-
phase2(s); // sort the sortable given the heap
-
-
return s; // return the Sortable for convenience
-
}
-
}
-
This class takes about one page of text in my VI text editor. Let's step back
a bit from this code and realize what we've just created: this sort algoritm is
very efficient and stable w.r.t. it's runtime. This implementation doesn't know
anything about what exactly needs to be sorted, i.e. it only uses the Sortable
interface.
The class is final and contains a private default constructor so there is no
way for anyone else to create an instance of a HeapSort object; because no such
object is needed: this class is a utility class with just functionality.
The first article explained a bit about the heap sort algorithm itself.
Now let's get back to our original problem: given the following two arrays:
-
String[] first= { "Fred", "Barney", "Wilma", "Betty", "Bambam", "Pebbles" };
-
String[] last= { "Flintstone", "Rubble", "FlintStone", "Rubble", "Rubble", "Flintstone" };
-
We have to create a Sortable that can return the number of first/last names, it
can compare two first names (for example) and it can swap two elements in both
the first and last name arrays. We need to sort these two array according to
the first name; the other array just needs to 'follow' i.e it last names must
correspond to the first names after the sort has finished.
Here's the complete example without many comments:
-
public class Flintstones implements Sortable {
-
-
private String[] first;
-
private String[] last;
-
-
public FlintStones(String[] first, String[] last) {
-
-
this.first= first;
-
this.last = last;
-
}
-
-
public int length() { // interface implementation
-
-
return first.length;
-
}
-
-
public int compare(int i, int j) { // interface implementation
-
-
return first[i].compareTo(first[j]);
-
}
-
-
private void swap (String[] s, int i, int j) { // private helper method
-
-
String t= s[i]; s[i]= s[j]; s[j]= t;
-
-
}
-
public void swap(int i, int j) { // interface implementation
-
-
swap(first, i, j);
-
swap(last, i, j);
-
}
-
-
public static void main(String[] args) {
-
-
String[] first= { "Fred", "Barney", "Wilma", "Betty", "Bambam", "Pebbles" };
-
String[] last= { "Flintstone", "Rubble", "FlintStone", "Rubble", "Rubble", "Flintstone" };
-
-
HeapSort.sort(new ArraySortable(first, last));
-
-
for (int i= 0; i < first.length; i++)
-
System.out.println(first[i]+" "+last[i]);
-
}
-
}
-
So what was this 'Tip Of The Week' all about? It showed that you can sort not
just arrays or Lists, but anything that implements the Sortable interface. It
also showed some of the gory details of the heap sort algorithm.
If I don't get kicked out now I'd like to tell something about permutations
and combinations in a next Tip Of The Week and how they can be efficiently
generated without much hassle.
kind regards,
Jos
