 |
| (Click or use local copy.) |
Programming Languages
Spring 2005
Recitation 9
Genericity in Java
Week 9: Mar 21-25
Due (on time): 2005-03-28 23:59:59
Due (late): 2005-04-01 23:59:59
|
CS 3723/3721 Programming Languages Spring 2005 Recitation 9 Genericity in Java Week 9: Mar 21-25 Due (on time): 2005-03-28 23:59:59 Due (late): 2005-04-01 23:59:59 |
Recitation 9 must be submitted
following directions at: submissions with deadlines
|
Here is an implementation of quicksort to sort an array of doubles: the class QuickSort. There is also a class to test the quicksort program and time its performance: QuickSortTest. Finally there is a class to generate the array of random doubles for sorting: RandomArray. Notice that the test of this program prints the first 20 elements of the sorted array, just to see what is going on with the array.
| Quicksort in Java | Test of Quicksort |
|---|---|
// QuickSort: carries out quicksort
public class QuickSort {
public void quicksort(double a[]) {
quicksort(a, 0, a.length - 1);
}
private void quicksort(double a[],
int low, int high) {
if (high >low) {
int pivot = partition(a, low, high);
quicksort(a, low, pivot-1);
quicksort(a, pivot+1, high);
}
}
private int partition(double a[],
int low, int high) {
int left, right;
double pivot_item = a[low];
int pivot = left = low;
right = high;
while ( left < right ) {
while(left < a.length - 1 &&
a[left] <= pivot_item) // Go left
left++;
while(a[right] > pivot_item) // Go right
right--;
if (left < right) swapRef(a, left, right);
}
// right is final position for the pivot
a[low] = a[right];
a[right] = pivot_item;
return right;
}
private void swapRef(double a[], int i, int j) {
double temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
|
// QuickSortTest: test the QuickSort class
public class QuickSortTest {
private int size;
private double[] a; // holds numbers to sort
private QuickSort q;
private RandomArray r;
public QuickSortTest(int s) {
size = s;
q = new QuickSort();
r = new RandomArray(size);
}
public void test() {
System.out.println("Number of items: " + size);
long startTime = System.currentTimeMillis();
a = r.getArray();
elapsedTime(startTime, "After generating, ");
q.quicksort(a);
elapsedTime(startTime, "After sorting, ");
System.out.println("Sorted is " + checkSorted(a));
r.printStart();
}
public boolean checkSorted(double a[]) { // check
for (int i = 0; i < a.length - 1; i++)
if (a[i] > a[i+1]) return false;
return true;
}
private void elapsedTime(long startTime, String s) {
long stopTime = System.currentTimeMillis();
double elapsedTime = ((double)(stopTime -
startTime))/1000.0;
System.out.println(s + "elapsed time: " +
elapsedTime + " seconds");
}
public static void main(String[] argv) {
int size = Integer.parseInt(argv[0]);
QuickSortTest qTest = new QuickSortTest(size);
qTest.test();
}
}
|
| Generate Array of Random doubles | Run of Quicksort Program |
|---|---|
// RandomArray: create random array for sorting
public class RandomArray {
private int size;
private double[] a; // holds numbers to sort
public RandomArray(int s) {
size = s;
a = new double[size];
generateArray();
}
private void generateArray() {
for (int i = 0; i < a.length; i++)
a[i] = Math.random();
}
public double[] getArray() {
return a;
}
public void printStart() {
int i = 0;
int limit = 20;
while (i < limit && i < size)
System.out.println(a[i++]);
}
}
| % javac RandomArray.java % javac QuickSort.java % javac QuickSortTest.java % java QuickSortTest 10000 Number of items: 10000 After generating, elapsed time: 0.0 seconds After sorting, elapsed time: 0.03 seconds Sorted is true 5.865593821074988E-5 1.042020746924166E-4 4.1564716955944103E-4 4.213473539347312E-4 4.378650461884792E-4 5.291359539935092E-4 6.681635307126399E-4 7.952195329985479E-4 8.553584593787855E-4 9.201910447078632E-4 9.543684852468814E-4 9.965954524646659E-4 0.001022836845252617 0.0012127191394349923 0.0014496001439885386 0.001600455985977911 0.0018413211880439206 0.00230446684187402 0.0023246475164687697 0.0023376480444526893 |
Below, I am supplying a class RandomArrayGeneric that returns either an array of double, and array of int, or an array of Rational, which is a user-defined class yielding fractions.
Thus for this recitation, you should rewrite the two classes QuickSort and QuickSortTest so that they will handle Comparable, instead of double. This means substituting Comparable for double, and also replacing any use of operators <, >, or ==, with calls to compareTo. Finally, you should use my supplied classes Rational and RandomArrayGeneric. Here is the source code for these classes:
| Generate Array of Random doubles, ints, or Rationals | Run of Generic Quicksort Program |
|---|---|
// RandomArrayGeneric: create random array
public class RandomArrayGeneric {
private int size;
private Comparable[] a; // holds nums to sort
//private Rational rat;
public RandomArrayGeneric(int s) {
size = s;
a = new Comparable[size];
//rat = new Rational();
generateArray();
}
private void generateArray() {
int u = (int)(3*Math.random());
if (u == 0)
for (int i = 0; i < a.length; i++) {
double r = Math.random();
a[i] = new Double(r);
}
else if (u == 1)
for (int i = 0; i < a.length; i++) {
int r = (int)(100000*Math.random());
a[i] = new Integer(r);
}
else
for (int i = 0; i < a.length; i++) {
int r = (int)(10000*Math.random()+1);
int s = (int)(10000*Math.random()+1);
a[i] = new Rational(r, s);
}
}
public Comparable[] getArray() {
return a;
}
public void printStart() {
int i = 0;
int limit = 10;
while (i < limit && i < size)
System.out.println(a[i++]);
}
}
| % java QuickSortGenericTest 1000 Number of items: 1000 After generating, elapsed time: 0.0010 seconds After sorting, elapsed time: 0.023 seconds Sorted is true 31 153 185 193 237 541 682 717 769 894 % java QuickSortGenericTest 1000 Number of items: 1000 After generating, elapsed time: 0.0010 seconds After sorting, elapsed time: 0.123 seconds Sorted is true 1/1640 1/690 13/8410 17/5445 7/2047 8/2151 25/6528 116/9453 117/7739 50/3201 % java QuickSortGenericTest 1000 Number of items: 1000 After generating, elapsed time: 0.0 seconds After sorting, elapsed time: 0.024 seconds Sorted is true 3.0750653380895443E-4 9.870541892926799E-4 0.0015971956149616329 0.0043003360164523 0.005414058974433811 0.010424925979375277 0.01049507542434791 0.016999031902315886 0.018596897865151174 0.019387306770027868 |
|
Contents of submission
for Recitation 9: Last Name, First Name; Course Number; Recitation Number. a. Source code for your altered versions of the classes QuickSort.java and QuickSortTest.java, assuming that you are using the classes Rational and RandomArrayGeneric unchanged from my supplied versions. (If you make any changes, supply the code here also.) b. Repeated runs until your executions include all three types.
|