Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Mastering 2D Point Sorting: A Hands-On Guide with Selection, Insertion, Merge, and QuickSort in Java

Learn how to sort 2D integer points and find the median coordinate point using four classic sorting algorithms in Java. This tutorial covers selection sort, insertion sort, merge sort, and quicksort with practical examples and performance tips.

2D point sorting median coordinate point selection sort Java insertion sort Java merge sort Java quicksort Java sorting algorithms comparison Java sorting tutorial point class comparable sorting 2D points assignment sorting in gaming sorting in AI Java AbstractSorter sorting performance benchmark

Introduction to Sorting 2D Integer Points

Sorting is a fundamental concept in computer science, and applying it to 2D points adds a layer of complexity that mirrors real-world problems like GPS coordinate processing, game object rendering, and data clustering. In this guide, we'll walk through a typical assignment: reading 2D integer points, sorting them by x and y coordinates separately using four sorting algorithms, and finding the median coordinate point (MCP). This tutorial is designed to help you understand the core ideas without giving away the full solution.

Understanding the Problem

You are given a set of points with integer coordinates in the range [-50, 50]. The goal is to find the point whose x-coordinate is the median of all x-coordinates and whose y-coordinate is the median of all y-coordinates. To do this, you must sort the points twice: once by x (using the same sorting algorithm) and once by y. The median is the element at index n/2 (integer division) in the sorted array.

For example, if you have 17 points, the median x-coordinate is at index 8 (0-based). This median point may not be an actual input point—it's a virtual point representing the center of the dataset. This concept is used in statistics, image processing, and even in AI for summarizing clusters.

Setting Up the Point Class

First, you need a Point class that implements Comparable. The compareTo method should compare points first by x, then by y (or vice versa). This is essential for sorting stability.

public class Point implements Comparable<Point> {
    private int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }
    public int getX() { return x; }
    public int getY() { return y; }
    @Override
    public int compareTo(Point other) {
        if (this.x != other.x) return this.x - other.x;
        return this.y - other.y;
    }
}

AbstractSorter and Four Sorting Algorithms

You'll implement an abstract class AbstractSorter that contains a points array and a pointComparator. The constructor copies the input array (throwing IllegalArgumentException if null or empty). The sort() method is abstract and implemented by each subclass.

Selection Sort

Selection sort repeatedly finds the minimum element and swaps it into place. It's O(n²) but simple.

public class SelectionSorter extends AbstractSorter {
    public SelectionSorter(Point[] pts) { super(pts); }
    @Override
    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. It's efficient for small datasets and nearly sorted data.

public class InsertionSorter extends AbstractSorter {
    public InsertionSorter(Point[] pts) { super(pts); }
    @Override
    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 with O(n log n) time. It's stable and great for large datasets.

public class MergeSorter extends AbstractSorter {
    public MergeSorter(Point[] pts) { super(pts); }
    private Point[] temp;
    @Override
    public void sort() {
        temp = new Point[points.length];
        mergeSort(0, points.length - 1);
    }
    private void mergeSort(int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSort(low, mid);
            mergeSort(mid + 1, high);
            merge(low, mid, high);
        }
    }
    private void merge(int low, int mid, int high) {
        for (int i = low; i <= high; i++) temp[i] = points[i];
        int i = low, j = mid + 1, k = low;
        while (i <= mid && j <= high) {
            if (pointComparator.compare(temp[i], temp[j]) <= 0)
                points[k++] = temp[i++];
            else
                points[k++] = temp[j++];
        }
        while (i <= mid) points[k++] = temp[i++];
    }
}

QuickSort

QuickSort is also O(n log n) on average but can be O(n²) in worst case. It's often the fastest in practice.

public class QuickSorter extends AbstractSorter {
    public QuickSorter(Point[] pts) { super(pts); }
    @Override
    public void sort() {
        quickSort(0, points.length - 1);
    }
    private void quickSort(int low, int high) {
        if (low < high) {
            int pi = partition(low, high);
            quickSort(low, pi - 1);
            quickSort(pi + 1, high);
        }
    }
    private int partition(int low, int high) {
        Point pivot = points[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (pointComparator.compare(points[j], pivot) <= 0) {
                i++;
                swap(i, j);
            }
        }
        swap(i + 1, high);
        return i + 1;
    }
}

PointScanner and Reading Input

The PointScanner class reads points from an array or a file. When reading from a file, ensure the number of integers is even. Use Scanner to parse integers.

public PointScanner(String fileName, Algorithm algo) throws FileNotFoundException, InputMismatchException {
    Scanner sc = new Scanner(new File(fileName));
    List<Integer> ints = new ArrayList<>();
    while (sc.hasNextInt()) ints.add(sc.nextInt());
    if (ints.size() % 2 != 0) throw new InputMismatchException();
    Point[] pts = new Point[ints.size() / 2];
    for (int i = 0; i < pts.length; i++)
        pts[i] = new Point(ints.get(2*i), ints.get(2*i+1));
    // Initialize sorter based on algo
}

Finding the Median Coordinate Point

After sorting by x, get the median x from the point at index n/2. Then sort by y and get the median y. The MCP is (medianX, medianY). Note that the median index is points.length / 2 (integer division).

public void scan() {
    // Sort by x
    setComparator(0); // 0 for x
    sort();
    int medianX = points[points.length / 2].getX();
    // Sort by y
    setComparator(1); // 1 for y
    sort();
    int medianY = points[points.length / 2].getY();
    medianCoordinatePoint = new Point(medianX, medianY);
}

Comparing Sorting Algorithms

The CompareSorters class runs all four algorithms on the same dataset and measures time using System.nanoTime(). This is crucial for understanding performance trade-offs. For a dataset of 10,201 points (the maximum possible), merge sort and quicksort will significantly outperform selection and insertion sorts.

In real-world applications, like processing player coordinates in a battle royale game or sorting location data for a ride-sharing app, choosing the right sorting algorithm can mean the difference between a smooth experience and lag. For example, when a game server needs to sort 1000 player positions every frame, an O(n log n) algorithm is essential.

Tips for Success

  • Start early to take advantage of extra credit. The assignment offers up to 10% extra credit for early submission.
  • Test with small datasets first, like the 17-point example provided.
  • Use the provided abstract class structure to avoid reinventing the wheel.
  • Benchmark your implementations to see the time differences. You might notice that insertion sort is faster than selection sort for nearly sorted data.
  • Handle edge cases: duplicate points, empty arrays, and odd number of integers in file.

Trend Connection: Sorting in AI and Gaming

Sorting algorithms are everywhere in modern tech. In AI, sorting is used for k-nearest neighbors where you sort distances to find the closest points. In gaming, sorting is used for z-buffering to render objects in the correct order. For example, in a game like Fortnite, the engine must sort all visible objects by depth each frame. Using an efficient quicksort or merge sort ensures smooth gameplay. Similarly, in machine learning pipelines, sorting data points by a feature is a common preprocessing step.

Conclusion

By implementing these four sorting algorithms for 2D points, you gain a deep understanding of how sorting works and how to choose the right tool for the job. Whether you're analyzing data, building a game, or working on an AI project, these skills are invaluable. Remember to test thoroughly and enjoy the process!