we have provided a file containing United States geographical data (specifically
ID: 3909167 • Letter: W
Question
we have provided a file containing United States geographical data (specifically, a comprehensive list of 80264 geographical locations identified by 5-digit zip code, city, state and latitude/longitude). Functionality has already been provided for processing this data file and creating an array of Location objects to hold this data. Each time you run the main method in the SortingPerformance class, a random selection of locations is loaded. The parameter n limits the number of locations loaded from the file so that you’ll be able to easily run experiments on different input sizes. You will be comparing four different sorting algorithms: selection sort, insertion sort, quick sort, and the sorting method provided by the JDK (Java Developer’s Kit, specifically the Arrays.sort(Object []) method). The selection sort algorithm and the method to call the JDK’s sorting algorithm have already been provided for you in the SortingAlgorithms class. Refer to the selection sort method especially if you are still unclear on how to use the compareTo method. You will need to adapt the insertion sort and quick sort algorithms from your text to sort Location objects in the given array (be sure to sort and return a copy of the array, not the array itself. 1.Implement the compareTo method in the Location class. 2. Implement the insertionSort and quickSortRecursive methods in the SortingAlgorithms class. 3.Debug your code and verify that each sorting algorithm is correctly sorting by using the printLocationArray method provided to you to output the array contents. ************************************************************************************************ public class Location implements Comparable { private final String zipCode; private final String city; private final Double latitude; private final Double longitude; private final String state; public Location(String zipCode, Double latitude, Double longitude, String city, String state) { this.zipCode = zipCode; this.city = city; this.latitude = latitude; this.longitude = longitude; this.state = state; } public String getCity() { return this.city; } public String getZipCode() { return this.zipCode; } public Double getLatitude() { return latitude; } public Double getLongitude() { return longitude; } public String getState() { return state; } /** * Complete the implementation of this method that will be used for sorting * using the java.util.Collections.sort method. * @param o * @return */ @Override public int compareTo(Location l) { throw new UnsupportedOperationException("YOU MUST IMPLEMENT THIS"); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(this.getCity()); sb.append(" "); sb.append(this.getState()); sb.append(", "); sb.append(this.getZipCode()); return sb.toString(); } } ****************************************************************************************************** import java.util.Arrays; public class SortingAlgorithms { public static Location [] javaSort(Location list[]) { Location result[] = Arrays.copyOf(list, list.length); Arrays.sort(result); return result; } public static Location [] selectionSort(Location list[]) { Location result[] = Arrays.copyOf(list, list.length); for(int i=0; i int minIndex = i; for(int j=i+1; j if(result[j].compareTo(result[minIndex]) < 0) minIndex = j; } Location tmp = result[i]; result[i] = result[minIndex]; result[minIndex] = tmp; } return result; } public static Location [] insertionSort(Location list[]) { Location result[] = Arrays.copyOf(list, list.length); //TODO: implement insertion sort here return result; } public static Location [] quickSort(Location list[]) { Location result[] = Arrays.copyOf(list, list.length); quickSortRecursive(result, 0, result.length-1); return result; } private static void quickSortRecursive(Location list[], int low, int high) { //TODO: implement quick sort here } } ******************************************************************************************************************* import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Scanner; public class SortingPerformance { private final Integer maxNumLocations; private Location locations[]; public SortingPerformance(Integer maxLocations) { this.maxNumLocations = maxLocations; this.locations = new Location[maxLocations]; loadFromFile(); } public Location[] getLocations() { return this.locations; } private void loadFromFile() { List tmp = new ArrayList(); try { File file = new File("data/geoData.csv"); Scanner scanner = new Scanner(file); //throw away first line scanner.nextLine(); while (scanner.hasNextLine()) { String line = scanner.nextLine(); //create airport objects String[] arr = line.split(","); Integer z = Integer.parseInt(arr[0]); String zip = String.format("%05d", z); Double lat = 0d; Double lon = 0d; String city = arr[3] == null ? "" : arr[3]; String state = arr[4] == null ? "" : arr[4]; try { lat = Double.parseDouble(arr[1]); lon = Double.parseDouble(arr[2]); } catch(NumberFormatException nfe) { //silence exceptions } Location location = new Location(zip, lat, lon, city, state); tmp.add(location); } } catch (FileNotFoundException e) { System.out.println(e); } Collections.shuffle(tmp); for(int i=0; i this.locations[i] = tmp.get(i); return; } public static void printLocationArray(Location list[]) { System.out.println(Arrays.toString(list)); } public static void main(String args[]) { int n = 400; SortingPerformance sp = new SortingPerformance(n); //TODO: setup your experiments here } }
Explanation / Answer
Answer:
Note: File "geoData.csv" is not given. I have createds the file on my own and ran the program.
Code:
File Name: Location.java
public class Location implements Comparable<Location>
{
private final String zipCode;
private final String city;
private final Double latitude;
private final Double longitude;
private final String state;
public Location(String zipCode, Double latitude, Double longitude, String city, String state)
{
this.zipCode = zipCode;
this.city = city;
this.latitude = latitude;
this.longitude = longitude;
this.state = state;
}
public String getCity()
{
return this.city;
}
public String getZipCode()
{
return this.zipCode;
}
public Double getLatitude()
{
return latitude;
}
public Double getLongitude()
{
return longitude;
}
public String getState()
{
return state;
}
/** * Complete the implementation of this method that will be used for sorting * using the java.util.Collections.sort method. * @param o * @return */
@Override
public int compareTo(Location l)
{
double ln2, lg2;
ln2 = l.getLatitude();
lg2 = l.getLongitude();
double d = findDistance(latitude, longitude, ln2, lg2);
if(d>1.00)
return 1;
return 0;
}
private double findDistance(double ln1, double lg1, double ln2, double lg2)
{
double tp1 = Math.toRadians(ln2-ln1);
double tp2 = Math.toRadians(lg2 - lg1);
double s1 = Math.sin(tp1/2);
double s2 = Math.sin(tp2/2);
double x = Math.pow(s1,2) + Math.pow(s2, 2) *Math.cos(Math.toRadians(ln1))*Math.cos(Math.toRadians(ln2));
double p = 2* Math.atan2(Math.sqrt(x), Math.sqrt(1-x));
double distance = 3958.75 * p;
return distance;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append(this.getCity());
sb.append(" ");
sb.append(this.getState());
sb.append(", ");
sb.append(this.getZipCode());
return sb.toString();
}
}
File Name: SortingAlgorithms.java
import java.util.Arrays;
public class SortingAlgorithms
{
public static Location [] javaSort(Location list[])
{
Location result[] = Arrays.copyOf(list, list.length);
Arrays.sort(result);
return result;
}
public static Location [] selectionSort(Location list[])
{
Location result[] = Arrays.copyOf(list, list.length);
for(int i=0; i<result.length; i++)
{
int minIndex = i;
for(int j=i+1; j <result.length; j++)
{
if(result[j].compareTo(result[minIndex]) < 0)
minIndex = j;
}
Location tmp = result[i];
result[i] = result[minIndex];
result[minIndex] = tmp;
}
return result;
}
public static Location [] insertionSort(Location list[])
{
Location result[] = Arrays.copyOf(list, list.length);
//TODO: implement insertion sort here
for(int j=1; j<result.length; j++)
{
Location tp = result[j];
int i = j -1;
while((i>-1)&&(tp.compareTo(result[i]) < 0) )
{
result[i+1] = result[i];
i--;
}
result[i+1] = tp;
}
return result;
}
public static Location [] quickSort(Location list[])
{
Location result[] = Arrays.copyOf(list, list.length);
quickSortRecursive(result, 0, result.length-1);
return result;
}
private static void quickSortRecursive(Location list[], int low, int high)
{
if(high> low)
{
int pIndx = partition(list, low, high);
quickSortRecursive(list, low, pIndx -1);
quickSortRecursive(list, pIndx + 1, high);
}
}
private static int partition(Location list[], int fst, int lst)
{
Location pivot = list[lst];
int i = fst-1;
for(int j= fst; j<lst; j++)
{
if(list[j].compareTo(pivot)<0)
{
i++;
Location tp = list[i];
list [i] = list[j];
list [j] = tp;
}
}
Location tp = list[i+1];
list [i+1] = list[fst];
list [fst] = tp;
return i+1;
}
}
File Name: SortingPerformance.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class SortingPerformance {
private final Integer maxNumLocations;
private Location locations[];
public SortingPerformance(Integer maxLocations) {
this.maxNumLocations = maxLocations;
this.locations = new Location[maxLocations];
loadFromFile();
}
public Location[] getLocations() {
return this.locations;
}
private void loadFromFile() {
List<Location> tmp = new ArrayList<Location>();
try {
File file = new File("geoData.csv");
Scanner scanner = new Scanner(file);
//throw away first line
scanner.nextLine();
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
//create airport objects
String[] arr = line.split(",");
Integer z = Integer.parseInt(arr[0]);
String zip = String.format("%05d", z);
Double lat = 0d;
Double lon = 0d;
String city = arr[3] == null ? "" : arr[3];
String state = arr[4] == null ? "" : arr[4];
try {
lat = Double.parseDouble(arr[1]);
lon = Double.parseDouble(arr[2]);
} catch(NumberFormatException nfe) {
//silence exceptions
}
Location location = new Location(zip, lat, lon, city, state);
tmp.add(location);
}
} catch (FileNotFoundException e) {
System.out.println(e);
}
Collections.shuffle(tmp);
for(int i=0; i<this.maxNumLocations; i++)
this.locations[i] = tmp.get(i);
return;
}
public static void printLocationArray(Location list[]) {
System.out.println(Arrays.toString(list));
}
public static void main(String args[]) {
int n = 6;
SortingPerformance sp = new SortingPerformance(n);
SortingAlgorithms sa = new SortingAlgorithms();
Location[] list = sp.getLocations();
System.out.println(" Locations sorted by java library:");
printLocationArray(sa.javaSort(list));
System.out.println(" Locations sorted by selection sort:");
printLocationArray(sa.selectionSort(list));
System.out.println(" Locations sorted by insertion sort:");
printLocationArray(sa.insertionSort(list));
System.out.println(" Locations sorted by quick sort:");
printLocationArray(sa.quickSort(list));
}
}
Sample Input file: geoData.csv
zip_code,latitude,longitude,city,state
501,40.922326,-72.637078,Holtsville,NY
601,18.165273,-66.722583,Adjuntas,PR
602,18.393103,-67.180953,Aguada,PR
603,18.455913,-67.14578,Aguadilla,PR
606,18.172947,-66.944111,Maricao,PR
610,18.288685,-67.139696,Anasco,PR
Sample Output:
Locations sorted by java library:
[Anasco PR, 00610, Adjuntas PR, 00601, Maricao PR, 00606, Aguadilla PR, 00603, Holtsville NY, 00501, Aguada PR, 00602]
Locations sorted by selection sort:
[Anasco PR, 00610, Adjuntas PR, 00601, Maricao PR, 00606, Aguadilla PR, 00603, Holtsville NY, 00501, Aguada PR, 00602]
Locations sorted by insertion sort:
[Anasco PR, 00610, Adjuntas PR, 00601, Maricao PR, 00606, Aguadilla PR, 00603, Holtsville NY, 00501, Aguada PR, 00602]
Locations sorted by quick sort:
[Anasco PR, 00610, Adjuntas PR, 00601, Maricao PR, 00606, Aguadilla PR, 00603, Holtsville NY, 00501, Aguada PR, 00602]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.