please read the attachment file for the assignmentLab 9 Due Wednesday by 11:59pm Points 3 ...

Question

please read the attachment file for the assignmentLab 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 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 Application: implements action listener  MyWindow: implements mouse listener Lab Submission:  *.java files with the lab solutions Files for this lab: Application.java   (https://canvas.uw.edu/courses/1541396/files/85904286/download? download_frd=1) , InterfaceDriver.java    (https://canvas.uw.edu/courses/1541396/files/85904292/download?download_frd=1) , Multi.java    (https://canvas.uw.edu/courses/1541396/files/85904287/download?download_frd=1) , MyArrayList.java    (https://canvas.uw.edu/courses/1541396/files/85904295/download?download_frd=1) , SortDiver.java    (https://canvas.uw.edu/courses/1541396/files/85904300/download?download_frd=1) , Student.java    (https://canvas.uw.edu/courses/1541396/files/85904289/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 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, we'll make https://canvas.uw.edu/courses/1541396/files/85904286?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904286/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904292/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904292/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904287/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904287/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904295?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904295/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904300/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904300/download?download_frd=1 https://canvas.uw.edu/courses/1541396/files/85904289/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904289/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 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. 1. Download the provided MyArrayList class, and inside of it declare a method called intBubbleSort() a. Note that MyArrayList has 3 arrays as its class fields; int[] , char[] , and String[] b. public void intBubbleSort()  //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 bubble sort method ii. Implement a helper method called “ public void swapInts ( int[] intList, int j ) ” to call from your intBubbleSort()  to swap the elements for you 2. Download the SortDiver.java   (https://canvas.uw.edu/courses/1541396/files/85904300/download? download_frd=1) which contains the main method to test your code. a. The arrays get populated with random values in constructor. b. Print the list out using toString();  it should appear unsorted. c. 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. 3. Now, change your code so that it sorts an ArrayList of Comparable objects. To do this, you’ll need to declare the ArrayList class as “ public class MyArrayList 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 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 b. 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/85904300/download?wrap=1 https://canvas.uw.edu/courses/1541396/files/85904300/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 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? 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 MyArrayList class :   Construct an outer for loop that traverses the array up to (n-1) element { 1. Construct an inner for loop that traverses the array 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 array[j] 0 && data[hole-1]  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 “@Override” , 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);”

Shweta · Accepted Answer

Answer Attached Below:

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...

Answer To: Lab 9 Due Wednesday by 11:59pm Points 3 Submitting a file upload Available Mar 4 at 12am - Mar 17 at...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment