Turn in assignment as both a hardcopy in class and a zipped file, using this link to cardea. Please have all your code as runnable .java files.
For these questions, I use pseudocode that is a bit more detailed than the usual thing, to help you with your coding.
You should complete parts (I) and (II) before doing part (III).
We have finessed this problem so far in our code, and will continue to do so in the first part of this assignment. In the second part of this assignment we will look at how to use java interfaces to address this issue.
So for the sorting in the first part of this assignment, I am asking you only to sort arrays of integers. (If you use Vectors you will have difficulty comparing if one component of a vector is greater or less than another.) In the second part of this assignment, we will use interfaces to allow comparison of arbitrary objects.
It is recursive because you have to assume you have a list in sorted order even though you don't have such a thing when you start. The trick is to start with an empty list and insert each item on the original list one at a time, keeping the list in sorted order as you go.
Questions:
InsertionSort
Input: a list of objects with keys (integers rather than objects in first part of assignment)
Output: a list of objects in sorted order according to their keys (integers in first part of assignment)
InsertionSort (list)
initialize newList
for each item in list
newList = InsertionSort(newList, item)
return newList
InsertionSort
Input: a list and an object to insert into sorted order.
Output: a sorted list
InsertionSort(a, key)
newArray[] = new int [a.length+1] [A]
while ((current < a.length) && (key > a[current])) [B]
newArray[current] = a[current]
increment current
newArray[current] = key;
while (current < a.length) [C]
newArray[current+1] = a[current] [D]
increment current
return newArray;
Questions:
Help for implementation: Below I show the Merge method in a lot of detail but the mergeSort method in a bit less detail. To do the splitting in the mergeSort method, I found it helpful to use the method System.arraycopy() which allows you to copy pieces of one array into another.
MergeSort(list)
if the length of the list is 1, then return the list
else
firsthalf = first half of list)
secondhalf = second half of list)
return Merge( mergeSort(firsthalf), mergeSort(secondhalf))
Merge(f, s)
newList = new int[f.length + s.length]
i = j = k = 0;
while ((i < f.length) or (j < s.length))
if (i >= f.length) [A]
newList[k] = s[j]
increment j
else if (j >= s.length) [B]
newList[k] = f[i]
increment i
else if (f[i] < s[j]) [C]
newList[k] = f[i]
increment i
else
newList[k] = s[j] [D]
increment j
increment k
return newlist
The issue is that you can't just say "if (object_a > object_b) ..." because there are any number of ways of comparing two objects. For example, if you have an class called Employee, you might want to sort instances of that class according to salary, name, ssid, etc. What we need is a mechanism for dealing with this problem. This is one place where java interfaces are useful.
import java.util.*;
public class GeneralQuickSort {
private Comparable a[];
GeneralQuickSort (int size) {
Random r = new Random();
int range = 1000;
a = new Comparable[size];
for (int i=0; i < size; i++) {
a[i] = new Integer(r.nextInt(range));
}
}
public void printQuickSort() {
for (int i=0; i < a.length; i++)
System.out.print(a[i].toString() + " ");
System.out.println();
}
public void quickSort (int left, int right) {
if (left > right)
return;
int partition = partitionArray(left, right);
quickSort(left, partition-1);
quickSort(partition+1, right);
}
public int partitionArray(int left, int right) {
Comparable pivot = a[left];
while (left < right) {
while (a[left].compareTo(pivot) < 0) left++;
while (a[right].compareTo(pivot) > 0) right--;
swap(left, right);
}
return left;
}
private void swap (int l, int r) {
Comparable temp = a[l];
a[l] = a[r];
a[r] = temp;
}
public static void main(String args[]){
GeneralQuickSort qs = new GeneralQuickSort(8);
System.out.println("Before Quicksort: ");
qs.printQuickSort();
qs.quickSort(0, qs.a.length-1);
System.out.println("After Quicksort: ");
qs.printQuickSort();
}
}
Note the use of compareTo().
As an example, I was working on some IR code that, after indexing a collection, builds a list of all the terms in the collection, along with the number of documents they are associated with. To keep track of this information, I created a class called TextInfo in which objects consist of a term (the word or phrase itself) and a count, indicating how many docs it occurs in (this is the DF term from IR). Since the index is a hash table, the list is not in sorted order when I build it.
I'd like to put this list in order of decreasing DF, and should be able to re-use the code I already wrote for sorting lists of integers. The way to do this is to change that code to sort lists of objects. That can be made to work if I
We use the java Comparable interface because many of the basic java types (such as String, File, Integer, etc) all implement this interface. If this weren't the case then we would have made up our own interface. Here's how to do it:
public class TextInfo implements Comparable {
private String term;
private int count;
TextInfo() {
term = "default";
count = 0;
}
TextInfo(String t, int c) {
term = t;
count = c;
}
public String getTerm () {
return term;
}
public int getCount(){
return count;
}
}
Note the implements Comparable declaration, which is critical. That tells the system that objects of class TextInfo can be cast into objects of type Comparable, because I have implemented the necessary methods to satisfy the interface for Comparable.
It turns out that the only thing I have to do to make this class implement the Comparable interface is to write a method called compareTo() that takes as input an object (in this case, of the same type as the one the method is defined on) and compares this object with the input object for order. More specifically, it returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the input object.
This is all I have to do, because this is all the definition of Comparable interface asks me to do. (For more details, including a list of which java types implement it, see the Java API for the Comparable interface.)
public int compareTo(Object to) {
// I don't really have to do this first cast since the method
// must be associated with an object of class TextInfo; I
// do it for readability.
TextInfo tia = (TextInfo) this;
// Have to cast the input object to the correct class
TextInfo tib = (TextInfo) to;
if (tia.getCount() == tib.getCount()) // check for equals
return 0;
if (tia.getCount() < tib.getCount()) // check for less than
return -1;
return 1; // otherwise greater than
}
I could have returned an appropriate value by specifying tia.getCount() - tib.getCount() but this doesn't work if the input can have negative values and can be problematic in terms of rounding errors if I were subtracting doubles.