Please help, and please make sure your code works. Thank you in advance! 6.1 Con
ID: 3692202 • Letter: P
Question
Please help, and please make sure your code works. Thank you in advance!
6.1 Consider the Point class discussed in Objects and Classes : Section 1 (in burger-cse205-note-objs-classes-01.pdf in the Week 1 Notes zip archive; the Point.java source code file can be found in the Week 1 Source Code zip archive). Modify this class so it implements the Comparable interface. We define Point p1 to be less than Point p2 if the distance from the origin to p1 is less than the distance from the origin to p2; p1 is greater than p2 if the distance from the origin to p1 is greater than the distance from the origin to p2; otherwise, if they distances are equal then p1 is equal to p2. Submit your modified source code file in your homework submission zip archive.
6.2 Consider this ArrayList of Integers, which is to be sorted into ascending order:
list = { 13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15 }.
Trace the insertionSort() method and show the contents of list: (1) on entry to insertionSort(); (2) after the for j loop terminates each time but before the for i loop is repeated; and (3) after the for i loop terminates. The objective of this exercise is to help you understand how the insertion sort algorithm sorts a list. 6.3 Your after-hours research finally pays off: you discover a way to build a computer system that is one billion times faster than the fastest system currently in existence. Therefore, on your new computer system each comparison of selection sort requires only 25 × 10-18 seconds, which is 25 attoseconds. Create a table similar to the one in Sorting Algorithms : Section 6 showing how long selection sort will require to sort various sized lists.
6.4 If we would like to require insertionSort() to sort a list of 10-billion elements in no more than one minute, how many times faster would your new computer system need to be than the fastest system currently in existence?
Explanation / Answer
// code version 1.0 for the first part of the question:
// Question 6.1) Answer:
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package point1;
import static java.lang.Math.sqrt;
import java.util.Scanner;
/**
*
* @author Admin
*/
public class Point1 {
static class Point {
private float p ,q, r;
Point(){
} // end constructor Point
Point(float p1, float q1) {
p = p1; q = q1; r = 0;
} // end 2 param constructor
void setter(float p1, float q1, float r1) {
p = p1; q = q1; r = r1;
} // end setter function
void findDistance(float p1, Float q1, float r1, float p2, float q2,float r2) {
float dist = (float)0.0, dist1FromOrigin = (float)0.0, dist2FromOrigin = (float)0.0;
//formulat for distance = sqrt((p2-p1)^2 + (q2-q1)^2 + (r2-r1)^2);
System.out.println("Point A coordinates are: " + p1 + q1 + r1);
System.out.println("Point B coordinates are: " + p2 + q2 + r2);
dist = (float) sqrt ((p2-p1)*(p2-p1) + (q2-q1)*(q2-q1) + (r2-r1)*(r2-r1));
System.out.println("The points are " + (dist) + " apart");
// distance of point A from Origin
dist1FromOrigin = (float) sqrt((p1-0)*(p1-0) + (q1-0)*(q1-0) + (r1-0)*(r1-0));
dist2FromOrigin = (float) sqrt((p2-0)*(p2-0) + (q2-0)*(q2-0) + (r2-0)*(r2-0));
System.out.println("Distance of point pt1 FROM origin = " + dist1FromOrigin);
System.out.println("Distance of point pt2 FROM origin = " + dist2FromOrigin);
if (dist2FromOrigin > dist1FromOrigin) System.out.println("Point 2 at the corordibnates = ( " + p2 + " , " + q2 + " , " + r2 + " ) is greater than point 1");
else if (dist2FromOrigin < dist1FromOrigin )
System.out.println("Point 1 at the corordibnates = ( " + p1 + " , " + q1 + " , " + r1 + " ) is greater than point 2");
else System.out.println("Point 1 is equal to point 2");
} // end findDistance function
} // end class Point
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Point pt1;
pt1 = new Point();
Point pt2;
pt2 = new Point();
Scanner sc = new Scanner(System.in);
float p1, q1,r1;
float p2, q2 , r2 ;
System.out.println("Enter the coordinates for A");
p1 = sc.nextFloat();
q1 = sc.nextFloat();
r1 = sc.nextFloat();
pt1.setter(p1, q1, r1); // initialire the point
System.out.println("Enter the coordinates for B");
p2 = sc.nextFloat();
q2 = sc.nextFloat();
r2 = sc.nextFloat();
pt2.setter(p2, q2, r2); // initialire the point
pt1.findDistance(p1, q1, r1, p2, q2, r2);
} // end main
} // end public class point1
run:
Enter the coordinates for A
1
3
5
Enter the coordinates for B
2
4
6
Point A coordinates are: 1.03.05.0
Point B coordinates are: 2.04.06.0
The points are 1.7320508 apart
Distance of point pt1 FROM origin = 5.91608
Distance of point pt2 FROM origin = 7.483315
Point 2 at the corordibnates = ( 2.0 , 4.0 , 6.0 ) is greater than point 1
BUILD SUCCESSFUL (total time: 6 seconds)
run:
Enter the coordinates for A
11
9
5
Enter the coordinates for B
1
2
3
Point A coordinates are: 11.09.05.0
Point B coordinates are: 1.02.03.0
The points are 12.369317 apart
Distance of point pt1 FROM origin = 15.066519
Distance of point pt2 FROM origin = 3.7416575
Point 1 at the corordibnates = ( 11.0 , 9.0 , 5.0 ) is greater than point 2
BUILD SUCCESSFUL (total time: 14 seconds)
run:
Enter the coordinates for A
1
4
2
Enter the coordinates for B
4
2
1
Point A coordinates are: 1.04.02.0
Point B coordinates are: 4.02.01.0
The points are 3.7416575 apart
Distance of point pt1 FROM origin = 4.582576
Distance of point pt2 FROM origin = 4.582576
Point 1 is equal to point 2
BUILD SUCCESSFUL (total time: 7 seconds)
// Question 6.2) Insertion sort
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package insertionsort;
import java.util.Arrays;
/**
*
* @author Admin
*/
public class InsertionSort {
static void insertSort(int [] arr) {
int i, j, item;
System.out.println("The list (array) on entry to insertion sort function :" + Arrays.toString(arr));
for (j=1; j<arr.length; j++) {
item = arr[j]; // store the jth value to item to be inserted in to the left array
System.out.println("List Contents after the for j loop terminates before i loop:" + Arrays.toString(arr));
for (i = j-1; (i>=0) && (arr[i] > item); i--)
arr[i+1] = arr[i]; // keep shifting them to the left
System.out.println("List Contents after the for i loop terminates:" + Arrays.toString(arr));
arr[i+1] = item;
} // end for j
System.out.println("The array in sorted order:" + Arrays.toString(arr));
} // end function insertSort
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
// int [] arr = new int[11];
int [] arr = {13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15 };
insertSort(arr);
}
}
// for (i = 0; i< arr.length; i++)
// System.out.print(arr[i] + " ," );
//for (i = 0; i< arr.length; i++)
// System.out.print(arr[i] + " ," );
run:
The list (array) on entry to insertion sort function :[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[13, 13, 75, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[12, 12, 13, 75, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 12, 13, 75, 75, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 12, 12, 13, 18, 75, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 12, 12, 13, 18, 75, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 9, 12, 12, 13, 18, 75, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 9, 9, 10, 12, 13, 18, 75, 14, 15]
List Contents after the for i loop terminates:[4, 6, 7, 9, 10, 12, 13, 18, 18, 75, 15]
List Contents after the for i loop terminates:[4, 6, 7, 9, 10, 12, 13, 14, 18, 18, 75]
The array in sorted order:[4, 6, 7, 9, 10, 12, 13, 14, 15, 18, 75]
BUILD SUCCESSFUL (total time: 0 seconds)
run:
The list (array) on entry to insertion sort function :[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[13, 13, 75, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[12, 13, 75, 4, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[12, 12, 13, 75, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 12, 13, 75, 18, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 12, 13, 75, 75, 6, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 12, 13, 18, 75, 6, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 12, 12, 13, 18, 75, 9, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 6, 12, 13, 18, 75, 9, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 12, 12, 13, 18, 75, 10, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 6, 9, 12, 13, 18, 75, 10, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 9, 12, 12, 13, 18, 75, 7, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 6, 9, 10, 12, 13, 18, 75, 7, 14, 15]
List Contents after the for i loop terminates:[4, 6, 9, 9, 10, 12, 13, 18, 75, 14, 15]
List Contents after the for j loop terminates before i loop:[4, 6, 7, 9, 10, 12, 13, 18, 75, 14, 15]
List Contents after the for i loop terminates:[4, 6, 7, 9, 10, 12, 13, 18, 18, 75, 15]
List Contents after the for j loop terminates before i loop:[4, 6, 7, 9, 10, 12, 13, 14, 18, 75, 15]
List Contents after the for i loop terminates:[4, 6, 7, 9, 10, 12, 13, 14, 18, 18, 75]
The array in sorted order:[4, 6, 7, 9, 10, 12, 13, 14, 15, 18, 75]
BUILD SUCCESSFUL (total time: 0 seconds)
run:
The array in sorted order:
4 ,6 ,7 ,9 ,10 ,12 ,13 ,14 ,15 ,18 ,75 ,BUILD SUCCESSFUL (total time: 0 seconds)
6.4) 10 billion = 10000000000
25 * 10 ^ -18 seconds per instruction
hence 10000000000 * 25 * 10 ^ -18 = 2.5 e -7
1 / 2.5 e ^ -7 = 0.000364753
Hence the new computer has to be 364,753 times faster than the fastest current system in existence