Part III: Tree Sort Complete the following two methods in a utility class (TreeSort.java): public static KeyedItem[] treeSort(KeyedItem[] unsorted) //convenience method to sort all of the items in the array (calls the next method)

public static KeyedItem[] treeSort(KeyedItem[] unsorted, int n) //sort the first n items in the array (check n for validity)

As a convenience to the user, the array passed in (unsorted) is not directly sorted. Instead, create a new array with size equal to the number of items to be sorted. Return this new array with the items in sorted order just in case the unsorted array is still needed by the user for some reason.

There is a potential problem with creating a new array and returning it to the user, however. You don't know the actual type of the objects in the array, just their supertype (KeyedItem). You can create and return an array of type KeyedItem[], but if the user needs a particular object in the sorted array, they will have to downcast from KeyedItem to the actual type of the object. If you need to process all of the items in the array, that is a lot of casting.

Instead, you can use the Class class and the Array class to figure out what the actual type of the objects in the array are, and create an array of that type. To get the type of the array, use the getComponentType() method in the Class class. Your driver will still need to downcast the array as a whole from KeyedItem[] to the type of the array, but you won't need to cast each individual object in the array. To accomplish this, refer to the Java API. Hint: you are interested in the newInstance() method in the Array class.

Refer to the BinarySearchTree documentation to create a BST that will allow duplicate keys and will preserve FIFO ordering for duplicate keys. Place all of the items from the unsorted array into the tree and perform the appropriate traversal to get the items back out in sorted order (look at the documentation for the Iterator and TreeIterator interfaces). Place the sorted items in the array that you instantiated and that will be returned to the user. What is the order notation for this sort? Is it stable?

//TreeSort.java

mport java.util.Iterator; import bst.*; import ki.KeyedItem;

public class TreeSort { //convenience method public static KeyedItem[] treeSort(KeyedItem[] sort) { }

public static KeyedItem[] treeSort(KeyedItem[] sort, int n) { //easier to use a KeyedItem array than Comparable //create a new Binary Search Tree //a balanced tree ensures logn inserts for nlogn sort

//need to use the Class class as the actual array type may be a subtype of KeyedItem // fill up the search tree

//pull sorted stuff out of the tree }

}

//keyed item class

package ki;

public abstract class KeyedItem { //create single instance variable of type Comparable public KeyedItem(Comparable key) { this.key = key; }

public Comparable getKey() { return key; }

//Use Comparable toString() method public String toString() { return key.toString(); } }