The skeleton code on gitlab is the start of a program to sort latitude/longitude coordinates based on distance to a starting point. An additional class, Coord, is included in the code. It holds information about the coordinate, including the value that you should sort by: the distance field. The distances are already calculated in the Coord array by the time a sorting algorithm is called. In order to sort the input array, change its order in-place. Instead of an explicit return value, the updated order of input array should be the result of the sorting method calls. There are two example algorithms: insertionSort Uses an O(n 2 ) sorting algorithm to sort the array. systemSort Calls Javas built-in sorting algorithm, which is a variant on quicksort. For this assignment, you will implement two sorting algorithms: quickSort and randQuickSort. You should implement quicksort as it is presented in the lecture slides or book: when partitioning, pick the left or right element in each subarray as the pivot. For randomized quicksort, use the Java Random class to generate a valid index in the subarray for each partition call and use that value as the randomly chosen pivot. You can write additional methods in A3.java to help with your solution. Do not edit anything in the Coord.java file.

package edu.wit.cs.comp2350;

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner;

public class A3 {

//TODO: document this method

public static void quickSort(Coord[] destinations) {

//TODO: implement this method

}

//TODO: document this method

public static void randQuickSort(Coord[] destinations) {

//TODO: implement this method

}

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

// Call system sort with a lambda expression on the comparator

public static void systemSort(Coord[] destinations) {

Arrays.sort(destinations, (a, b) -> Double.compare(a.getDist(), b.getDist()));

}

// Insertion sort eventually sorts an array

public static void insertionSort(Coord[] a) {

for (int i = 1; i < a.length; i++) {

Coord tmpC = a[i];

int j;

for (j = i-1; j >= 0 && tmpC.getDist() < a[j].getDist(); j--)

a[j+1] = a[j];

a[j+1] = tmpC;

}}

private static Coord getOrigin(Scanner s) {

double lat = s.nextDouble();

double lon = s.nextDouble();

Coord ret = new Coord(lat, lon);

return ret;

}

private static Coord[] getDests(Scanner s, Coord start) {

ArrayList a = new ArrayList<>();

while (s.hasNextDouble()) {

a.add(new Coord(s.nextDouble(), s.nextDouble(), start));

}

Coord[] ret = new Coord[a.size()];

a.toArray(ret);

return ret;

}

private static void printCoords(Coord start, Coord[] a) {

System.out.println(start.toColorString("black"));

for (int i = 0; i < a.length; ++i) {

System.out.println(a[i].toColorString("red"));

}

System.out.println();

System.out.println("Paste these results into http://www.hamstermap.com/custommap.html if you want to visualize the coordinates.");

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

System.out.printf("Enter the sorting algorithm to use [i]nsertion sort, [q]uicksort, [r]andomized quicksort, or [s]ystem quicksort): ");

char algo = s.next().charAt(0);

System.out.printf("Enter your starting coordinate in \"latitude longitude\" format as doubles: (e.g. 42.3366322 -71.0942150): ");

Coord start = getOrigin(s);

System.out.printf("Enter your end coordinates one at a time in \"latitude longitude\" format as doubles: (e.g. 38.897386 -77.037400). End your input with a non-double character:%n");

Coord[] destinations = getDests(s, start);

s.close();

switch (algo) {

case 'i':

insertionSort(destinations);

break;

case 'q':

quickSort(destinations);

break;

case 'r':

randQuickSort(destinations);

break;

case 's':

systemSort(destinations);

break;

default:

System.out.println("Invalid search algorithm");

System.exit(0);

break;

}

printCoords(start, destinations);

}

For coordinates:

Package edu.wit.cs.comp2350;

// holds information about the earth latitude/longitude about a coordinate

public class Coord {

private double latitude;

private double longitude;

private String name;

private double dist;

/**

Basic constructor for a Coord, which sets the lat and lon, and sets the

distance of the Coord to 0

@param lat The latitude of the coordinate

@param lon The longitude of the coordinate

*/

public Coord(double lat, double lon) {

latitude = lat;

longitude = lon;

dist = 0;

name = "start";

}

/**

Constructor for a Coord, which sets the lat and lon, and sets the

distance of the Coord to the distance to the origin parameter in km

@param lat The latitude of the coordinate

@param lon The longitude of the coordinate

@param origin The coordinate that the distance of the Coord should be based on

*/

public Coord(double lat, double lon, Coord origin) {

latitude = lat;

longitude = lon;

dist = distTo(this, origin);

name = "unnamed";

}

/**

Constructor for a Coord, which sets the lat and lon, and sets the

distance of the Coord to the distance to the origin parameter in km

@param lat The latitude of the coordinate

@param lon The longitude of the coordinate

@param origin The coordinate that the distance of the Coord should be based on

@param n The name of the location

*/

public Coord(double lat, double lon, Coord origin, String n) {

latitude = lat;

longitude = lon;

dist = distTo(this, origin);

name = n;

}

/**

Getter for the dist variable in the Coord

@return the distance of the Coord to its start location

*/

public double getDist() {

return dist;

}

// return the distance in km from here to there (assumes earth is spherical)

private double distTo(Coord here, Coord there) {

final int R = 6371; // Radius of the earth

double lat1 = here.latitude; double lon1 = here.longitude;

double lat2 = there.latitude; double lon2 = there.longitude;

Double latDistance = Math.toRadians(lat2 - lat1);

Double lonDistance = Math.toRadians(lon2 - lon1);

Double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)

+ Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))

* Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);

Double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

double distance = R * c;

return distance;

}

/**

equality operator based on the latitude/longitude info only

@param that the Coord to compare lat/lon against

@return true iff the Coords match exactly

*/

public boolean equals(Coord that) {

return this.latitude == that.latitude && this.longitude == that.longitude;

}

/**

@return a comma-separated latitude/longitude string

*/

public String toString() {

return String.format("%.7f,%.7f", latitude, longitude);

}

/**

@return a comma-separated latitude/longitude string with the Coord's name tacked on

*/

public String toNamedString() {

return String.format("%.7f,%.7f (%s)", latitude, longitude, name);

}

public String toColorString(String color) {

return String.format("%.7f\t%.7f\tcircle3\t%s\t\t%s", latitude, longitude, color, name);

}}