How to apply comparator to get the TOP 5 cities from a List sorted by population?

Question

I have a class City

public final class City {
private final String name;
private final String state;
private final int    population;

public City(String name, String state, int population) {
    this.name       = name;
    this.state      = state;
    this.population = population;
}
public String getName() {
    return name;
}
public String getState() {
    return state;
}
public int getPopulation() {
    return population;
}
@Override
public String toString() {
    return "City [name=" + name + ", state=" + state + ", population=" + population + "]";
}
}

And a class that implements Observable (not needed for this). This observable class holds an arraylist List<City> cityList that has the data for all the cities that have been reported.

My class TopFiveCities is supposed to:

"implement a getter method getTopFive() returning a list with the five top cities (in terms of population) received. The list is sorted from higher to lower numbers. The returned list must be a copy of the list kept by the observer"

Aside from just getting the top 5 list, I also need to know how to make a copy of that list from the observer.

This is what I have:

public class TopFiveCities
implements Observer {

// THIS ALSO DOESN'T WORK UNLESS THE LIST IS STATIC
// SO HOW CAN I MAKE A COPY OF THE LIST FROM OBSERVER?
private List<City> list = new ArrayList<>(CensusOffice.cityList);

public List<City> getTopFive() {
    Collections.sort(list, new Comparator<City>() {

        @Override
        public int compare(City o1, City o2) {
            return Integer.compare(o1.getPopulation(), o2.getPopulation());
        }
        
    });
    return list;
}

public void update(Observable observable) {
    if (!(observable instanceof Observable)) {
        throw new IllegalArgumentException();
    }
}
}

With this, when one of the sample outputs should be:

City [name=Chicago, state=IL, population=2746388]

I just receive a list of all the cities, sorted by population from LOWEST to HIGHEST. What I'm doing wrong?

@AndyTurner in the code I don't because I don't understand how to do that. But the list may also have less than 5 things (like my example output where it should just be the one city) — John Smith, Mar 24 '22 at 15:54
As I remember compare gets -1, 0, 1 values if you want to sort it highest to lowest then you can change compartor. Also you can get top 5 from the list — Gurkan İlleez, Mar 24 '22 at 15:55
@Gurkanİlleez okay, but How do you change it? / how do I get the top 5? — John Smith, Mar 24 '22 at 15:56
Okay that seems easy enough, so that just leaves making a copy of the list held by the observer (without that list being static), and changing the comparator @Gurkanİlleez — John Smith, Mar 24 '22 at 16:00
@Gurkanİlleez I tried that, it doesn't work because I still need to use Collections.sort() to be able to make it sorted by the population — John Smith, Mar 24 '22 at 16:01
@Gurkanİlleez it's better to use a reversed comparator than to reverse the list after sorting it. — Andy Turner, Mar 24 '22 at 16:02
https://stackoverflow.com/questions/32995559/reverse-a-comparator-in-java-8 — Gurkan İlleez, Mar 24 '22 at 16:03
I don't really thing that can work too well but MAYBE if I knew how to copy that list from the observer so I could actually test it. — John Smith, Mar 24 '22 at 16:11
You don’t need `Collections` utility class. `List` offers a `sort` method. — Basil Bourque, Mar 24 '22 at 17:10

score 1 · Accepted Answer · answered Mar 24 '22 at 16:56

1

You can just use a Stream, use a Comparator to sort the stream, limit the number of element and convert the elements to a new list:

List<City> top5citiesByPopulation = cities.stream()
        .sorted(Comparator.comparing(City::getPopulation).reversed())
        .limit(5)
        .collect(Collectors.toList());

answered Mar 24 '22 at 16:56

David SN

3,389
1
17
21

Streams are likely not appropriate to this apparent schoolwork assignment. – Basil Bourque Mar 24 '22 at 17:03
@BasilBourque And this problem also doesn't require sorting. – Alexander Ivanchenko Mar 24 '22 at 21:00

score 0 · Answer 2 · answered Mar 24 '22 at 16:39

int order = requestedOrder.equals("asc") ? 1 : -1;

Collections.sort(list, new Comparator<CustomObj>() {
    public int compare(CustomObj first, CustomObj scnd) {
        return first.getComparableParam().compareTo(scnd.getComparableParam()) * order;
    }
});

I just copied and passed this code block from recommended stackover page in the comment. Of you want ascending order simply change it. In your code order will be -1.

Simply you need to multiply by -1.

return Integer.compare(o1.getPopulation(), o2.getPopulation()) * -1;

After this you can sublist it.

You keep the list as global variable it can be reached from update method but it does not change if class is singleton except for update method. Your update method can change it by notifying

In update method you can simply clear and add new list by list.addAll

Basil Bourque · Answer 3 · 2022-03-24T17:08:43.910

Since this is a schoolwork assignment, I’ll describe the pieces but let you assemble them into final code.

I have a class "City"

You could more briefly define that class as a record.

City ( String name, String state, int population ) {}

holds an array list "List cityList"

List < City > cities = new ArrayList<>();

getting the top 5 list

Sort the list by using a reverse comparator. You can make a comparator for sorting by using a method reference for the accessor “getter” method. But be aware that records do not use the word “get” by default as their accessor, they use simply the name of the property.

cities.sort( Comparator.comparing( City :: population ).reversed() ) ;

For an unmodifiable list, call List.of or List.copyOf.

List#subset gives you a list with some of the elements of the original. But beware: the resulting list is based on a view of the original list. The subset is not separate and independent. To get a separate list, pass to List.copyOf or pass to the constructor of another List implementation.

List< City > topFivePop = List.copyOf( subset ) ;

Alexander Ivanchenko · Answer 4 · 2022-03-24T22:03:16.223

This problem doesn't require sorting the whole given list, which will have a time complexity of O(n log n).

Basically, the task is somewhat similar to finding the maximum element in the list that can be done in O(n) time with a single pass through the given list.

The most suitable approach for this problem is a partial sorting, and the best performance that could be achieved is the middle-ground between O(n) and O(n log n).

In order to find 5 maximum elements in a list, we can maintain a collection that will store in sorted order up to 5 previously encountered elements with maximum values.

Elements that are lover than the smallest element in the collection will be discarded automatically if the collection is already of size 5. Only new elements with a value higher than the smallest element's value will trigger reordering of this tiny collection. I.e. the data will be sorted partially instead of sorting the whole data set.

In the implementation below for as collection that will store 5 max elements, I've chosen a PriorityQueue.

According to the documentation it's methods have the following time complexity.

this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

I.e. adding of a new element and removing the first element both will perform in logarithmic time, and accessing the smallest value in the queue with the method element() with done in O(1) time (almost immediately).

The PriorityQueue is encapsulated inside a generic class, which constructor expects as parameters a Comparator<T> and a desired maximum size of the queue (i.e. a number of max elements that needs to be found).

The queue itself doesn't exposed to the outside classes. Method addItem() processing the given element and getFirstN returns a sorted immutable list.

Comparator in the code below is implemented using the static method comparingInt(). You could also implement Comparator in a "classical way" (pre-Java 8) by providing the behavior for it's abstract method compare() either by using a lambda expression or within an anonymous inner class.

public class FirstN<T> {
    private final Queue<T> queue;
    private final Comparator<T> comparator;
    private final int capacity;

    public FirstN(Comparator<T> comparator, int capacity) {
        this.queue = new PriorityQueue<>(comparator);
        this.comparator = comparator;
        this.capacity = capacity;
    }

    public boolean addItem(T item) {
        if (capacity == queue.size() && comparator.compare(item, queue.element()) <= 0) {
            return false; // queue is full and the given item is smaller than the lowerest element in the queue
        }

        if (capacity == queue.size() && comparator.compare(item, queue.element()) > 0) {
            queue.remove(); // removing the first element if it's smaller than the given item
        }
        return queue.add(item); // adding the given item
    }

    public List<T> getFirstN() {
        List<T> result = new ArrayList<>(queue); // creating a list based on a queue
        result.sort(comparator);
        return List.copyOf(result); // making a copy of the list (returned list is immutable)
    }
}

main()

public static void main(String[] args) {
    List<City> cities = List.of(
            new City("Austin", "Texas", 1028225),
            new City("Los Angeles", "California", 3985516),
            new City("San Diego", "California", 1429653),
            new City("Houston", "Texas", 2325353),
            new City("Phoenix", "Arizona", 1759943),
            new City("New York City", "New York", 8177025),
            new City("San Antonio", "Texas", 1598964),
            new City("Philadelphia", "Pennsylvania", 1585480),
            new City("San Diego", "California", 1429653),
            new City("Chicago", "Illinois", 2671635),
            new City("Dallas", "Texas", 1348886));

    FirstN<City> top5Cities =
            new FirstN<>(Comparator.comparingInt(City::getPopulation), 5);

    for (City next: cities) {
        top5Cities.addItem(next);
    }

    List<City> result = top5Cities.getFirstN(); // contains 5 biggest US cities

    result.forEach(System.out::println); // printing the result
}

Output (order from lowest to highest)

City [name=Phoenix, state=Arizona, population=1759943]
City [name=Houston, state=Texas, population=2325353]
City [name=Chicago, state=Illinois, population=2671635]
City [name=Los Angeles, state=California, population=3985516]
City [name=New York City, state=New York, population=8177025]

How to apply comparator to get the TOP 5 cities from a List sorted by population?

4 Answers4