Lab 9
Due Wednesday by 11:59pm Points 3 Submitting a file upload
Available Mar 4 at 12am - Mar 17 at 12:59am 13 days
Start Assignment
CSSSKL 143 Lab: Sorting and Interfaces
The lab consists of the following sections:
Segment 1: Sorts
Bu
le Sort
Selection Sort
Big O of Bu
le 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
Application: implements action listener
MyWindow: implements mouse listene
Lab Submission: *.java files with the lab solutions
Files for this lab: Application.java (https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?
download_frd=1) , InterfaceDriver.java
(https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1) , Multi.java
(https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1) , MyA
ayList.java
(https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1) , SortDiver.java
(https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1) , Student.java
(https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1)
Segment 1: Sorting
Summary
The purpose of this lab is to practice implementing the sorts we’ve covered in class. We’ll start by
uilding a simple Bu
le 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, we'll make
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
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 Bu
le Sort
The Bu
le 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 “bu
le” 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 afte
the first pass, so we are able to optimize on this search by only inspecting neighbors in the unsorted part
of the a
ay (the unsorted partition). This sort grows the sorted partition by one element (the largest)
each pass and shrinks the unsorted partition accordingly.
1. Download the provided MyA
ayList class, and inside of it declare a method called intBu
leSort()
a. Note that MyA
ayList has 3 a
ays as its class fields; int[] , char[] , and String[]
. public void intBu
leSort()
needs no input, as the list is instance data
i. See the pseudocode in the book or the slides for help on how to implement the bu
le sort
method
ii. Implement a helper method called “ public void swapInts ( int[] intList, int j ) ” to call
from your intBu
leSort() to swap the elements for you
2. Download the SortDiver.java (https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?
download_frd=1) which contains the main method to test your code.
a. The a
ays get populated with random values in constructor.
. Print the list out using toString(); it should appear unsorted.
c. In driver, uncomment the call to your intBu
leSort () method and output the list, this time in
sorted order. Be sure to get the co
ect output.
3. Now, change your code so that it sorts an A
ayList of Comparable objects. To do this, you’ll need to
declare the A
ayList class as “ public class MyA
ayList implements Comparable ” and implement the
compareTo() method to determine if one object is “less than” a second object.
4. 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?
5. Uncomment the driver, and test your compareTo() .
6. Optimizations
a. 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”?
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?wrap=1
https:
canvas.uw.edu/courses/1541396/files/ XXXXXXXXXX/download?download_frd=1
i. For example, the list {3 1 2} will need the outer loop to execute only one time, and not n(==3)
times
7. Now, refer to the method headings in MyA
ayList class and implement bu
le sort for chars and
Strings, as well. Do we need a separate swap() for Strings, since Strings are compared differently
than primitive types?
8. 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.
a. Use the following pseudo code to implement your selection sort inside MyA
ayList class :
Construct an outer for loop that traverses the a
ay up to (n-1) element {
1. Construct an inner for loop that traverses the a
ay up to the last element (n)
2. Does the inner loop iterator start at 0 or 1? Why?
3. Inside your loop check to see element at a
ay[j] < a
ay[i];
4. Assign the index number for the smallest value to a variable.
5. Keep updating the variable that holds the index for the smallest element as you continue
traversing the a
ay
6. When inner loop is completed, you will have the index for the smallest element in the a
ay
7. Now, all you have to do it use the swap() and swap a
ay[smallest index] with a
ay[i]
8. 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:
1. void swap(a
[], int index1, int index2)
2. int findSmallest(a
[], int begin, int end)
eturns the index of the smallest element
i. minIndex = begin;
hint
ii. for i = start to end
c. Finally, let’s make an improvement to the Selection Sort. In findSmallest, since we’re walking the
length of the unsorted partition, why not track both the smallest and the largest items we’ve seen? It’s
a few more compares per iteration, but we know from our Big O series that this won’t make the time
complexity any worse. In our new version, we may need to change the outermost loop so that it calls
findSmallest() and findLargest() .
d. 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 co
ect spot. So, our strategy will be outlined and
developed below by our pseudocode below; if you think you’ve 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 XXXXXXXXXXpartition
Once the neighbor is in the right place, we’re (locally) sorted and its time to repeat this process
InsertionSort Implementation
1. In the same A
ayList class, declare a method called insertionSort() ;
2. Implement the above (or below) pseudocode logic in your code
3. In your main test driver, change the code so that it invokes the InsertionSort.
a. Test your code
InsertionSort Pseudocode, Iteration 2
for(int a = 0; a < length – 1; a++) {
note -1 here since we’re dealing with neighbors (a, a+1)
int cu
ent = data[a];
int hole = a;
while( hole >0 && data[hole-1] < cu
ent ) {
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. We’ll start with an example using Students and the {Comparable, Cloneable}
interfaces, then move on to a
ief 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 thei
GPA and then sort a collection of students in order relative to their GPAs.
1. Build a Student Class with only two data items: a String name and a double GPA.
2. Modify the class definition so that it “implements Comparable”
3. When designing the compareTo() method, use the GPA to determine if student1 > student2
a. Consider returning the difference between the two students as the magnitude of difference
(either positive or negative)
4. Build main to test your Students, and in this main build a list of 10 Students with different GPAs
5. 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. We’ll do the first one together, which
is making students cloneable.
1. Add “implements Cloneable” to your Student class definition
2. Define the clone method using “@Ove
ide” , make it public and return a new student object
a. Build a copy constructor and then the clone is just one line of code
i. “return new Student(this);”