CompSci-61B Lab 5b
Recursive Sorts

Instructor: Prof. Robert Burns

In this assignment you will continue work on the "utility" class, compsci61b.MyUtilities. You will add methods implementing recursive sorting algorithms.

This assignment is worth 40 points, and consists of 4 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab5b.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.


EXERCISE 1: Merge Sort (10 points)
Add to MyUtilities.java a method that implements the recursive merge sort algorithm for linked lists. Use the following code block shells. 
public static <T extends Comparable<? super T>> void mergeSort(MyList<T> a)
{
  if (a instanceof MyLinkedDataStructure)
    mergeSortL(a);
  else
    throw new UnsupportedOperationException("MyUtilities.mergeSort is supported for linked structures only");
}

private static <T extends Comparable<? super T>> void mergeSortL(MyList<T> list) // O(n log(n))
{
  statements go here...
}
Add a main test method to create a "MyList" object of your choosing, populate it with some random values, sort and print. Compile, jar as lab5b.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 2: Quick Sort For Linked Lists (10 points)
Add to MyUtilities.java a method that implements the quick sort algorithm for linked lists. Use the following code block shell. 
public static <T extends Comparable<? super T>> void quickSort(MyList<T> a)
{
  if (a instanceof MyArrayBasedDataStructure)
    quickSortA(a, 0, a.size() - 1);
  else if (a instanceof MyLinkedDataStructure)
    quickSortL(a);
  else
    throw new UnsupportedOperationException("MyUtilities.quickSort is supported for array-based and linked structures only");
}

private static <T extends Comparable<? super T>> void quickSortA(MyList<T> a, int s, int e) // O(n log(n))
{
  no statements go here until the next exercise...
}

private static <T extends Comparable<? super T>> void quickSortL(MyList<T> list) // O(n log(n))
{
  statements go here...
}
Expand main to test these new methods. Compile, jar as lab5b.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 3: Quick Sort For Arrays (10 points)
Complete the "quickSortA" private method in MyUtilities.java that was left empty in the previous exercise. Use the following code block shell already provided above. Expand main to test this new method. Compile, jar as lab5b.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 4: Timing Studies For Recursive Sorting Algorithms (10 points)
Write compsci61b.testing.RecursiveSortingTimingTests.java, similar to lab 4's compsci61b.testing.TimingTests.java. Determine and include output statements for the big-oh of each of the following:
  1. mergeSort of a compsci61b.MyLinkedList
  2. quickSort of a compsci61b.MyLinkedList
  3. quickSort of a compsci61b.MyArrayList

Perform timing tests on each to confirm your determination of the big oh. Use the spec from lab 4's exercises 5-8.

For example: 

quickSort of a compsci61b.MyArrayList, O(n log n)
   n   big oh  elapsed time in millis  elapsed time / big oh norm
----  -------  ----------------------  --------------------- ----
1000     3000                    1324                  0.441 1.00
2000     6602                    2900                  0.439 1.00
4000    14408                    6370                  0.442 1.00
8000    31224                   13998                  0.448 1.02
Create your final version of lab5b.jar, with files from this and all previous labs. Post your lab5b.jar file to your student UNIX account for grading and credit.

[ Home | Contact Prof. Burns ]