Sort array of objects by any given field with counting sort

user_11343655 0
Viewed 133

I am trying to sort an array of Points by either the x, y, or z coordinate. This would be pretty clean with a comparison-based sort because I would just specify a custom comparator lambda. However, I am using counting sort.

I know how to implement the code to sort by any of the 3 coordinates. However, I don't want to copy paste the same method 3 times. Is there a way to generalize the same method to work on all 3 fields?

Here is my code for x:

private static Point[] sortX(Point[] arr, int max) {
    int[] cnt = new int[max+1];
    for(Point ele : arr) cnt[ele.x]++;
    for(int i = 1;i<cnt.length; i++) cnt[i] += cnt[i-1];
    
    Point[] ret = new Point[arr.length];
    for(int i = arr.length-1; i>=0; i--)
    {
        Point ele = arr[i];
        int sortBy = ele.x;
        ret[cnt[sortBy] - 1] = ele;
        cnt[sortBy]--;
    }
    return ret;
}

The idea I had was to take another array as the sortBy, with the same length as arr. Then I could create this array using x, y, or z coordinates, or something else entirely. However, I don't like this because there is too much stuff being done outside the method.

Another idea I had was to make Point have a get method like so:

public int get(char c) {
    if(c == 'x') return x;
    if(c == 'y') return y;
    if(c == 'z') return z;
    return -1;
}

Then I could make my counting sort take in a char parameter of either 'x', 'y', or 'z'.

This should be pretty common right? So what is the regular way of doing it?

counting-sort sorting java
1 Answers

You could pass a valueFunc into the sort method that will return the desired value from the Point depending on the given func.

e.g.

private static Point[] sortX(Point[] arr, int max, Function<Point, Integer> valueFunc) {
        int[] cnt = new int[max+1];
        for(Point ele : arr) cnt[valueFunc.apply(ele)]++;
        for(int i = 1;i<cnt.length; i++) cnt[i] += cnt[i-1];

        Point[] ret = new Point[arr.length];
        for(int i = arr.length-1; i>=0; i--)
        {
            Point ele = arr[i];
            int sortBy = valueFunc.apply(ele);
            ret[cnt[sortBy] - 1] = ele;
            cnt[sortBy]--;
        }
        return ret;
    }

Usage

sortX(points, 100, p -> p.y);
sortX(points, 100, p -> p.x);
sortX(points, 100, p -> p.z);
user_53856250
Related