Assignment: Sorting Points in the Plane
1. Overview
In computational geometry, algorithms often build their efficiency on processing geometric objects in certain orders that are generated via sorting. For example, Graham's scan constructs the convex hull of a number of input points in the plane in one traversal ordered by polar angle; intersection of a large number of line segments is performed using a sweeping line that makes stops at the endpoints of these segments that are ordered by x- or y- coordinate.
In this project, you are asked to sort an input set of points in the plane using the four sorting algorithms presented in class: selection sort, insertion sort, merge sort, and quick sort. Point comparison is based on either the x-coordinate or the polar angle with respect to some reference point. Your code should provide both options for comparison.
We make the following two assumptions:
(a) All input points have integral coordinates ranging between -50 and 50 inclusive.
(b) The input points may have duplicates.
Integral coordinates are assumed to avoid issues with floating-point arithmetic. The rectangular range [-50, 50] x [-50, 50] is big enough to contain 10, 201 points with integral coordinates. Since the input points will be either generated as pseudo-random points or read from an input file, duplicates may appear.
2. Compare Sorting Algorithms
The class CompareSorters executes the four sorting algorithms on points randomly generated or read from files. Over each input sequence, its main() method compares the execution times of these algorithms in multiple rounds. Each round proceeds as follows:
(a) Create an array of randomly generated integers, if needed.
(b) For each of the four classes SelectionSorter, InsertionSorter, MergeSorter, and QuickSorter, create an object of the class from the above array or an input file.
(c) Have the four created objects call the sort() method and store their results respectively in the files select.txt, insert.txt, merge.txt, and quick.txt.
3. Random Point Generation
To test your code, you may generate random points within the range [-50, 50] x [-50, 50]. Such a point has its x- and y-coordinates generated separately as pseudo-random numbers within the range [-50, 50]. To generate random numbers you need to import the java.util.Random class.
4. Display in Mathematica
The sorted points can be displayed in Mathematica. This will help you visualize the geometry and check the correctness of sorting. The software is licensed by ISU and available to students. To install Mathematica on your computer, please follow the instructions in the online document.
Attachment:- Assignment Files.rar