View RSS Feed

JosAH's blog

Heap Sort II

Rate this Entry
by , 06-12-2011 at 09:54 AM (2270 Views)
Greetings,

This is the second part of the Heap Sort article (that dumb forum software only allows 10000 characters per article part. Here's the second part:

The first part of this article explained a bit about the heap sort algorithm itself. Now let's get back to our original problem: given the two arrays:

Java Code:
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 arrays according to the first name; the other array just needs to 'follow' i.e its last names must correspond to the first names after the sort has finished.

Here's the complete example without many comments:

Java Code:
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 FlintStones(first, last));

		for (int i= 0; i < first.length; i++)
			System.out.println(first[i]+" "+last[i]);
	}
}
So what was this artice 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. This Sortable interface can even be implemented by something that stores its data on disk.

kind regards,

Jos

Submit "Heap Sort II" to Facebook Submit "Heap Sort II" to Digg Submit "Heap Sort II" to del.icio.us Submit "Heap Sort II" to StumbleUpon Submit "Heap Sort II" to Google

Updated 06-12-2011 at 04:30 PM by JosAH

Tags: None Add / Edit Tags
Categories
Uncategorized

Comments

  1. JavaForums's Avatar
    • |
    • permalink
    that dumb forum software only allows 10000 characters per article part
    Thanks for the feedback ;)
    It was the default value. I disabled that limit with a couple of others now..
  2. JosAH's Avatar
    • |
    • permalink
    Good to read; is there any other (small) maximum number of characters now or can I just type away? ;-)

    kind regards,

    Jos
  3. JavaForums's Avatar
    • |
    • permalink
    There is no limit now... You can write a book.. :)