CompSci-61B Lab 5a
Iterative Sorts

Instructor: Prof. Robert Burns

In this assignment you will begin work on a "utility" class, similar to the "java.util.Collections" class in the Java library. The class is not used for creating objects -- instead it is a compilation of stand-alone methods that act on "MyList" objects. The methods are implementations of the various searching and sorting techniques that we will study in ComscSci-61B.

The class to be started in this lab assignment is compsci61b.MyUtilities. Here is the container for the class: 

// javac compsci61b/MyUtilities.java
// java -ea compsci61b.MyUtilities
// jar cf compsci61b.jar compsci61b/*
// java -cp compsci61b.jar compsci61b.MyUtilities

identification comments go here...

package compsci61b;

public class MyUtilities
{
  methods go here...
}
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 lab5a.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: Selection Sort (10 points)
Add to MyUtilities.java a method that implements the nested for-loop selection sort algorithm. Use the following code block shell. 
public static <T extends Comparable<? super T>> void selectionSort(MyList<T> a)
{
  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 lab5a.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 2: Insertion Sort (10 points)
Add to MyUtilities.java a method that implements the insertion sort algorithm. Use the following code block shell. 
public static <T extends Comparable<? super T>> void insertionSort(MyList<T> a)
{
  statements go here...
}
Expand main to test this new method. Compile, jar as lab5a.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 3: Shell Sort (10 points)
Add to MyUtilities.java a method that implements the shell sort algorithm. Use the following code block shell. 
public static <T extends Comparable<? super T>> void shellSort(MyList<T> a)
{
  statements go here...
}
Expand main to test this new method. Compile, jar as lab5a.jar, and run, but do not submit -- the program will be further developed in the following exercises.

EXERCISE 4: Timing Studies For Iterative Sorting Algorithms (10 points)
Write compsci61b.testing.IterativeSortingTimingTests.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. insertionSort of a compsci61b.MyArrayList
  2. insertionSort of a compsci61b.MyLinkedList
  3. selectionSort of a compsci61b.MyArrayList
  4. shellSort 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, with nicely-aligned columns and 2 decimal digits in the last column's values.

For example: 

insertionSort of a compsci61b.MyArrayList, O(n-squared)
   n     big oh   elapsed time in millis   elapsed time / big oh  norm
----  ---------   ----------------------   ---------------------  ----
1000    1000000                     1324                   1.324  1.00
2000    4000000                     5436                   1.359  1.03
4000   16000000                    20784                   1.299  0.98
8000   64000000                    86120                   1.345  1.02
Create your final version of lab5a.jar, with files from this and all previous labs. Post your lab5a.jar file to your student UNIX account for grading and credit.

[ Home | Contact Prof. Burns ]