Mastering Sorting Algorithms for 2D Points: A COMS228 Homework Guide

Understanding the Median Coordinate Point Problem

In COMS228 Homework 2, you are tasked with finding the median coordinate point (MCP) from a set of 2D integer points. This involves sorting the points by their x-coordinates and y-coordinates separately, then taking the median of each. The MCP is not necessarily one of the input points; it's the point whose x-coordinate is the median of all x-coordinates and whose y-coordinate is the median of all y-coordinates. This problem tests your ability to implement and compare four fundamental sorting algorithms: selection sort, insertion sort, merge sort, and quicksort.

Why Sorting Algorithms Matter

Sorting is a cornerstone of computer science, used in everything from organizing data in databases to optimizing search algorithms. In this assignment, you'll see how different sorting algorithms perform on small to medium-sized datasets (up to 10,201 points). The insights you gain will help you choose the right algorithm for real-world applications, such as sorting leaderboards in gaming, ranking search results, or organizing financial transactions.

Setting Up the Point Class

The Point class implements the Comparable interface. Its compareTo() method compares points first by x-coordinate, then by y-coordinate. This is crucial for sorting by either coordinate using the same comparator logic.

public class Point implements Comparable<Point> {
    private int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }
    public int compareTo(Point other) {
        if (this.x != other.x) return Integer.compare(this.x, other.x);
        return Integer.compare(this.y, other.y);
    }
}

The AbstractSorter Hierarchy

You'll create an abstract class AbstractSorter that stores the array of points and provides the sorting framework. Four subclasses implement the specific algorithms: SelectionSorter, InsertionSorter, MergeSorter, and QuickSorter. Each subclass must call the superclass constructor and implement the sort() method.

Implementing the Constructor

The constructor copies the input array to avoid modifying the original. It throws IllegalArgumentException if the array is null or empty.

protected AbstractSorter(Point[] pts) throws IllegalArgumentException {
    if (pts == null || pts.length == 0) throw new IllegalArgumentException();
    points = new Point[pts.length];
    System.arraycopy(pts, 0, points, 0, pts.length);
}

Comparator and Sorting by Coordinate

The setComparator() method sets a comparator that compares points by x or y. You can use a lambda or anonymous class.

public void setComparator(int coordinate) {
    if (coordinate == 0) // x
        pointComparator = (p1, p2) -> Integer.compare(p1.getX(), p2.getX());
    else // y
        pointComparator = (p1, p2) -> Integer.compare(p1.getY(), p2.getY());
}

Implementing the Four Sorting Algorithms

Selection Sort

Selection sort repeatedly finds the minimum element and swaps it into place. It's simple but O(n²), making it slow for large datasets.

public void sort() {
    for (int i = 0; i < points.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < points.length; j++) {
            if (pointComparator.compare(points[j], points[minIdx]) < 0)
                minIdx = j;
        }
        swap(i, minIdx);
    }
}

Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position. It's also O(n²) but performs well on nearly sorted data.

public void sort() {
    for (int i = 1; i < points.length; i++) {
        Point key = points[i];
        int j = i - 1;
        while (j >= 0 && pointComparator.compare(points[j], key) > 0) {
            points[j + 1] = points[j];
            j--;
        }
        points[j + 1] = key;
    }
}

Merge Sort

Merge sort is a divide-and-conquer algorithm that splits the array, sorts each half recursively, and merges them. It's O(n log n) and stable.

private void mergeSort(Point[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Quicksort

Quicksort picks a pivot and partitions the array into elements less than and greater than the pivot. Average O(n log n), but worst-case O(n²) if poorly implemented.

private void quickSort(Point[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

The PointScanner Class

PointScanner reads points from an array or file and performs two rounds of sorting to find the MCP. It measures the total sorting time in nanoseconds.

public void scan() {
    // Sort by x
    sorter.setComparator(0);
    long start = System.nanoTime();
    sorter.sort();
    long end = System.nanoTime();
    scanTime += end - start;
    medianX = sorter.getMedian().getX();

    // Sort by y
    sorter.setComparator(1);
    start = System.nanoTime();
    sorter.sort();
    end = System.nanoTime();
    scanTime += end - start;
    medianY = sorter.getMedian().getY();

    medianCoordinatePoint = new Point(medianX, medianY);
}

Comparing Sorting Algorithms with CompareSorters

The CompareSorters class runs all four algorithms on the same dataset and prints statistics. This allows you to see which algorithm is fastest for different input sizes and distributions.

public static void main(String[] args) {
    // Generate random points
    Point[] pts = generateRandomPoints(1000);
    
    // Create scanners with different algorithms
    PointScanner scSel = new PointScanner(pts, Algorithm.SelectionSort);
    PointScanner scIns = new PointScanner(pts, Algorithm.InsertionSort);
    PointScanner scMer = new PointScanner(pts, Algorithm.MergeSort);
    PointScanner scQuc = new PointScanner(pts, Algorithm.QuickSort);
    
    // Scan each
    scSel.scan();
    scIns.scan();
    scMer.scan();
    scQuc.scan();
    
    // Print stats
    System.out.println(scSel.stats());
    System.out.println(scIns.stats());
    System.out.println(scMer.stats());
    System.out.println(scQuc.stats());
}

Performance Analysis and Trends

In practice, merge sort and quicksort outperform selection and insertion sort for larger datasets. For example, sorting 10,000 points (the maximum allowed) will show significant time differences. This mirrors real-world scenarios: imagine sorting a leaderboard for a popular video game like Fortnite or Valorant – efficient sorting ensures fast updates. Similarly, financial apps like Robinhood sort stock data to display real-time rankings. Understanding these algorithms helps you build efficient systems.

Common Pitfalls and Tips

• Null or empty input: Always check for null or empty arrays in constructors.
• Comparator consistency: Ensure the comparator used in sorting matches the coordinate you intend to sort by.
• Median index: Remember that the median index is points.length / 2 (integer division).
• Duplicate points: The problem allows duplicates; your sorting must handle them correctly.
• Timing precision: Use System.nanoTime() for accurate measurements. Run multiple trials and average.

Extra Credit: Early Submission

You can earn up to 10% extra credit by submitting up to 10 days early. Start early to avoid last-minute stress and to have time for thorough testing.

Tip: Use the extra time to experiment with different input sizes and observe how the sorting algorithms scale. This will deepen your understanding and help you write a better report.

Conclusion

This homework gives you hands-on experience with four classic sorting algorithms. By implementing them for 2D points, you'll learn about comparator design, algorithm complexity, and performance measurement. These skills are directly applicable to coding interviews and real-world software development. Good luck!