Description
The lab consists of the following sections:
- Segment 1: Sorts
- Bubble Sort
- Selection Sort
- Big O of Bubble and Selection
- Insertion Sort
- Segment 2: Interfaces
- Student Class: implements comparable, cloneable, and serializable + answers to serializable questions
- Quiz Score + Quiz Tracker: implements cloneable
- A class that implements runnable
- MyWindow: implements action listener
Lab Submission: *.java files with the lab solutions
Files for this lab: Application.java, InterfaceDriver.java, Multi.java, MyArrayList.java, SortDiver.java, Student.java
Segment 1: Sorting
Summary
The purpose of this lab is to practice implementing the sorts weve covered in class. Well start by building a simple Bubble Sort, which can be accomplished in 9 lines of code (LOC) or less, and then move on to more advanced sorting techniques like the Selection sort and Insertion sort. Also, well make minor improvements to the sorts to obtain better average-case execution times, but it is left as an exercise to the reader to demonstrate that these optimizations will have no effect on the (worst-case) Big O analysis.
Beginning with the Bubble Sort
The Bubble Sort is named due to how its sorting mechanism moves data items around during its sorting procedure. Heavy items sink to the bottom while smaller items bubble their way to the top by comparing neighbors and checking for inversions that is, two elements out of order that require a swap. By comparing successive neighbors, we are guaranteed the max element in the last place after the first pass, so we are able to optimize on this search by only inspecting neighbors in the unsorted part of the array (the unsorted partition). This sort grows the sorted partition by one element (the largest) each pass and shrinks the unsorted partition accordingly.
- Download the provided MyArrayList class, and inside of it declare a method called
intBubbleSort()
- Note that MyArrayList has 3 arrays as its class fields;
int[]
,char[]
, andString[]
public void intBubbleSort()
//needs no input, as the list is instance data- See the pseudocode in the book or the slides for help on how to implement the bubble sort method
- Implement a helper method called
public void swapInts ( int[] intList, int j )
to call from yourintBubbleSort()
to swap the elements for you
- Note that MyArrayList has 3 arrays as its class fields;
- Download the SortDiver.java which contains the main method to test your code.
- The arrays get populated with random values in constructor.
- Print the list out using
toString();
it should appear unsorted. - In driver, uncomment the call to your
intBubbleSort ()
method and output the list, this time in sorted order. Be sure to get the correct output.
- Now, change your code so that it sorts an ArrayList of Comparable objects. To do this, youll need to declare the ArrayList class as
public class MyArrayList implements Comparable
and implement thecompareTo()
method to determine if one object is less than a second object. - In your
compareTo()
use the following logic to compare the objects:if(this.IntList[0] < other.IntList[0]) return -1;else if(this.IntList[0] > other.IntList[0]) return 1;else return 0;
Explain in your code what does each one of these return values mean? Why 1, or -1, or 0?
- Uncomment the driver, and test your
compareTo()
. - Optimizations
- Can you reduce the inner loop relative to the outer loop? Try it
- Can you rewrite the outer loop so that it never executes additional times if the list is sorted early?
- For example, the list {3 1 2} will need the outer loop to execute only one time, and not n(==3) times
- Now, refer to the method headings in MyArrayList class and implement bubble sort for chars and Strings, as well. Do we need a separate
swap()
for Strings, since Strings are compared differently than primitive types? - Uncomment the driver, and test these newly created methods too
The Selection Sort
The selection sort makes progress by growing a sorted partition and shrinking the unsorted remainder. It does so by traversing the unsorted partition looking for the least element in that partition. The first pass simply looks for the least element and swaps that with the element at the head of the list (which is now considered sorted). The second pass would scan the remainder n-1 elements looking for the next minimum element, which then becomes the second element to the right of the head (now a 2-element sorted list), and so on until sorted.
- Use the following pseudo code to implement your selection sort inside MyArrayList class :Construct an outer for loop that traverses the array up to (n-1) element {
- Construct an inner for loop that traverses the array up to the last element (n)
- Does the inner loop iterator start at 0 or 1? Why?
- Inside your loop check to see element at
array[j] < array[i];
- Assign the index number for the smallest value to a variable.
- Keep updating the variable that holds the index for the smallest element as you continue traversing the array
- When inner loop is completed, you will have the index for the smallest element in the array
- Now, all you have to do it use the
swap()
and swap array[smallest index] with array[i] - Your loop will now go back to outer loop and will continue its work
- Now, use the following pseudo code to implement the two functions that the selection sort will need to iterate:
- void swap(arr[], int index1, int index2)
- int findSmallest(arr[], int begin, int end) //returns the index of the smallest element
- minIndex = begin; //hint
- for i = start to end
- Finally, lets make an improvement to the Selection Sort. In findSmallest, since were walking the length of the unsorted partition, why not track both the smallest and the largest items weve seen? Its a few more compares per iteration, but we know from our Big O series that this wont make the time complexity any worse. In our new version, we may need to change the outermost loop so that it calls
findSmallest()
andfindLargest()
. - Now compare the two sorts. The improvement we made in (3) should speed up the average-case execution of this algorithm, but does this improve the Big O for this algorithm? Build a Big O estimate using the estimation techniques covered in class, tracking the number of compares the new algorithm uses versus the standard selection sort.
InsertionSort
In this section, we will explore a new sorting implementation that grows a sorted partition by one at each step. As we expand our sorted partition to include our nearest neighbor, our partition becomes unsorted until we put the newest neighbor in the correct spot. So, our strategy will be outlined and developed below by our pseudocode below; if you think youve got a handle on the mechanism, try to implement the code after looking at just the first iteration of the pseudocode below. Look at the second iteration (spoiler alert!) if stumped.
InsertionSort Pseudocode, Iteration 1
Starting with the first node, ending with the last
- Get its neighbor (i+1)
- While the neighbor is out of place, move it backwards through the sorted partition
- Once the neighbor is in the right place, were (locally) sorted and its time to repeat this process
InsertionSort Implementation
- In the same ArrayList class, declare a method called
insertionSort()
; - Implement the above (or below) pseudocode logic in your code
- In your main test driver, change the code so that it invokes the InsertionSort.
- Test your code
InsertionSort Pseudocode, Iteration 2
for(int a = 0; a < length 1; a++) {//note -1 here since were dealing with neighbors (a, a+1) int current = data[a]; int hole = a; while( hole >0 && data[hole-1] < current ) { //while out of place //slide data to the left moving the hole left }}
Segment 2: Interfaces
Summary
This lab is designed to introduce you to some frequently encountered Interfaces in Java, and then to get familiar with writing your own interfaces. When a class implements the Comparable interface, we are able to sort objects of this set; if a class implements Cloneable, then we can call clone() to make copies of such an object. Well start with an example using Students and the {Comparable, Cloneable} interfaces, then move on to a brief introduction to multithreading (also using Interfaces).
Implementing the Comparable Interface for Sorting
We start by building a Student class that tracks their name and GPA, and then turn to implementing the Comparable Interface for this class. The idea is that we should be able to compare two students by their GPA and then sort a collection of students in order relative to their GPAs.
- Build a Student Class with only two data items: a String name and a double GPA.
- Modify the class definition so that it implements Comparable
- When designing the
compareTo()
method, use the GPA to determine if student1 > student2- Consider returning the difference between the two students as the magnitude of difference (either positive or negative)
- Build main to test your Students, and in this main build a list of 10 Students with different GPAs
- Download and run the InterfaceDriver to test comparing students (comparableDemo in code)
Implementing the Cloneable Interface
There are two examples in this section for the Cloneable interface. Well do the first one together, which is making students cloneable.
- Add implements Cloneable to your Student class definition
- Define the clone method using @Override , make it public and return a new student object
- Build a copy constructor and then the clone is just one line of code
- return new Student(this);
- Build a copy constructor and then the clone is just one line of code
- Run the corresponding driver code to test Student clones.
In this next example, well build two classes that implement the Cloneable Interface. The QuizTracker class contains an ArrayList of QuizScore objects, and its up to us to build these two classes so that we can make deep copies of QuizTrackers (and share no internal aliases). The key idea here is that to make deep copies of compound objects (or lists of objects), we need to copy (using clone) every object in every list, and even make copies of the list objects (ArrayLists here) themselves.
- Start by building a small QuizScore Class that contains only one data item: an int that corresponds to the score received on the quiz.
- Build a second class, QuizTracker, that contains an ArrayList of QuizScore objects (ArrayList) as its only data item
- This is just like an IntList covered previously, but instead of ints well be storing QuizScores and instead of arrays we can use an ArrayList here.
- Add getters and setters to QuizScore for the score, and provide an add(QuizScore) method for class QuizTracker (note: once done with (4), return to this step to be sure you add a clone of the QuizScore handed as input to this function to avoid privacy leaks
- Implement the Cloneable Interface for the QuizScore class
- This should not use ArrayList.clone(), as this is a shallow copy.
- Instead, to create a copy of a QuizTracker, you must first build a new ArrayList for the copy, and
- For each QuizScore object stored in our list, call
clone()
on each and add theclone()
to the newly created ArrayList in (b)
- For each QuizScore object stored in our list, call
- In this way, if we make a copy of the container (ArrayList), and all the contents in the container (QuizScores), weve succeeded in producing a deep copy for the QuizTracker class.
The Serializable Interface
To Serialize objects, we must first indicate that this is a permissible operation for our class. Certain classes should never be frozen to disk, such as real-time bank transactions or pacemaker operations. Java asks that you specifically indicate its ok to write your object to disk using this Tagging interface. Such an interface has no methods, but serves to identify sets of objects. Writing an object to disk requires a FileOutputStream()
to write bytes to a file decorated by an ObjectOutputStream()
, which will translate Objects to bytes for the FOS. This chain of operations looks like the diagram below.
To create an Object writer, use the code:
ObjectOutputStream os = new ObjectOutputStream(new FileOutputStream("data.obj"));
And to correspondingly read those objects, consider the code:
ObjectInputStream is = new ObjectInputStream(new FileInputStream("data.obj"));
- Go to your Student.java file and add implements Serializable
- Note that no additional coding is required
- Run the corresponding driver code from your set of interface drivers.
- What was ypur output?
- What did we accomplish?
The Runnable Interface
In this section, well build a class that can be run along other threads in a multithreaded (or multi-core) architecture. In Java, there exists a Thread class that we can extend and override to provide Thread specific activities, but even easier than this (and preferred) is to implement the Runnable Interface. The Runnable Interface has only one method (run()
), and any object that is Runn-able can be handed to a Thread Constructor and is queued for concurrent execution.
- Build a class that implements Runnable
- Make a constructor for this class that takes a string, and save this string to print out later (well use this to determine which thread is executing based on the string)
- Make the class do something interesting inside Runnable, such as print out the string passed to the constructor and print some calculation to the console
- If your class is named Foo, build two threads in the form:
Thread t1 = new Thread( new Foo() ));
- To start the execution of the t1 thread, invoke
t1.start();
- To start the execution of the t2 thread, invoke
t2.start();
- For extra guidance here, or to compare your code with another solution, see Multi.java for a working example.
Implementing Interfaces Using ActionListener
Implementing interfaces is one technique Java uses to allow for multiple inheritance. In this section, well be working with a Window Class (called a JFrame) that has only one GUI component added to it: a JButton. When you download and run this code, pressing the button currently does nothing. In this section, your job is to modify the Application Class so that it will handle the buttons events. This class will need to implement the ActionListener interface, and then we can attach or register this event handler with the button were interested in.
- Extend the Application Class so that it implements ActionListener
- Define the ActionListener method
public void actionPerformed(ActionEvent e)
for the Application Class- Make this function do something noticeable, like pop up a JOptionPane message dialog, so you know when your class is actually being called to handle events.
- In the code, look for and uncomment the line of code that looks like:
myButton.addActionListener( this );
Implementing the MouseListener Class
In this section, well build a JFrame that can respond to mouse events such as a mouse click, a mouse rollover, etc.
- Build a new class called MyWindow that extends JFrame
- Use this class definition to get started:
import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import java.awt.event.MouseMotionListener; import javax.swing.JFrame; public class MyWindow extends JFrame implements MouseListener { public MyWindow() { setSize(400,400); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setVisible(true); //addMouseListener(this); } //todo: add MouseListener methods (see outline below)
- Add the following method stubs (to be filled out later)
Method Summary (Links to an external site.)
void mouseClicked(MouseEvent e) Invoked when the mouse button has been clicked (pressed and released) on a component void mouseEntered(MouseEvent e) Invoked when the mouse enters a component. void mouseExited(MouseEvent e) Invoked when the mouse exits a component. void mousePressed(MouseEvent e) Invoked when a mouse button has been pressed on a component void mouseReleased(MouseEvent e) Invoked when a mouse button has been released on a component - In your JFrame constructor, add the line
addMouseListener(this);
- In mouseClicked, add a
System.out.println()
so when the user clicks on the JFrame something is outputted to the console. - Declare an instance variable:
ArrayList myShapes = new ArrayList();
- When the user clicks on the JFrame, add a new student to the student ArrayList
- Grab the mouse x,y using the event object handed to your mouseClicked function and use it as the gpa.