Sorting a recursive list of objects by string property in Java

Question

I've a recursive list of objects with unknown depth and I'm trying to sort all objects within the lists by a string property name.

exampleData.json

[
    {
        "name": "B",
        "items": [
            {
                "name": "Bb",
                "items": []
            },
            {
                "name": "Bc",
                "items": []
            },
            {
                "name": "Ba",
                "items": []
            }
        ]
    },
    {
        "name": "A",
        "items": [
            {
                "name": "Ab",
                "items": []
            },
            {
                "name": "Aa",
                "items": []
            }
        ]
    }
]

sortedData.json

[
    {
        "name": "A",
        "items": [
            {
                "name": "Aa",
                "items": []
            },
            {
                "name": "Ab",
                "items": []
            },
            {
                "name": "Ac",
                "items": []
            }
        ]
    },
    {
        "name": "B",
        "items": [
            {
                "name": "Ba",
                "items": []
            },
            {
                "name": "Bb",
                "items": []
            }
        ]
    }
]

Below is my current approach in Java. While it seems to work for small amounts of data, I'm uncertain of how professional it is since I've no experience with recursion and its performance.

    private void sortRecursivelyByName(List<Item> items) {
        if(items== null || items.isEmpty()) {
            return;
        }
        items.sort((a,b) -> {
            this.sortRecursivelyByName(a.items);
            this.sortRecursivelyByName(b.items);
            return a.getName().compareTo(b.getName());
        });
    }

Izruo · Accepted Answer · 2022-05-04 09:22:28Z

You can certainly improve the performance by not doing the recursive calls in the Comparator implementation. When the list sorts itself, it will most likely consult this Comparator multiple times for the same item, so all of the nested lists will be sorted multiple times.

Instead, propagate the recursion manually.

private void sortRecursivelyByName(List<Item> items) {
    if (items == null || items.isEmpty()) {
        return;
    }
    for (Item item : items) {
        sortRecursivelyByName(item.items);
    }
    items.sort(Comparator.comparing(Item::getName));
}

The performance impact of a recursive approach, if any, is dependent on the recursion depth and should be neglectable unless you are somewhere in the thousands. Conveniently, your recursion depth is equal to your input depth, so you might be able to tell, how likely that is going to happen.

And even then, if the lists are sufficiently large, the sorting will take most of the time, and that would not change in an iterative approach.

Collectives™ on Stack Overflow

Sorting a recursive list of objects by string property in Java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related