Counting sort in java for tuples

Question

Hi, I am building a class that has a mapping of strings to integers. So if I have 3 apples I would have a mapping of apples to 3.

I need to write a class that sorts the name of the objects by decreasing numbers.

So if I have

(apples, 3) (oranges, 2) (bananas, 5)

I will get (bananas, 5), (apples, 3), (oranges 2)

I was wondering if there's already a class out there that would make my life easier or how I would implement this.

Thanks.

Answer 1

You really want to take a look at TreeMap.

Assuming the counts are unique, you simply reverse the tuples, storing the count as the key and the name of the fruit as the value. TreeMap then stores the items sorted in ascending order by the key value, and you can read the values back. Since the sorting is done on the insertion the retrieval time is very low.

If you have non-unique counts there's an easy solution here that will let you take advantage of TreeMap.

Answer 2

You should be able to put your objects (apples, 3) (oranges, 2) (bananas, 5) into a List and then call Collections.sort(yourlist). You'd then want to make sure the object you declared implements the Comparable interface.

More information is available at http://java.sun.com/docs/books/tutorial/collections/interfaces/order.html

Let's say you declared you object as

import java.util.*;

public class FruitAndCount implements Comparable<FruitAndCount> {
    private final String _name;
    private final int _count;

    public FruitAndCount(String name, int count) {
       this._name = name;
        this._count = count;
    }

    public String name() { return _name; }
    public String count()  { return _count;  }

    public int compareTo(FruitAndCount comp) {
        return this._count.compareTo(comp.count);
    }
}

You should then be able to make the following call which will sort your list:

FruitAndCount fruitArray[] = {
    new FruitAndCount("Apples", 3),
    new FruitAndCount("Oranges", 2),
    new FruitAndCount("Bananas", 5)
};

List<FruitAndCount> fruit = Arrays.asList(fruitArray);
Collections.sort(fruit);

You should then have a sorted list of fruit.

Warning: Syntax errors may be present. I have not tested any of the above code.

Answer 3

It's always nice to be able to make a class implement Comparable, but sometimes you can't, or it is undesirable (for instance, if you need to be able to compare the same type in different ways, based on different attributes).

In this case, it is advisable to use the overloaded Collections.sort() method, which takes a List<T> to sort and a Comparator<T> to determine how the objects should be sorted. This is much cleaner than making new tuples out of your old tuples, and can be more flexible than implementing Comparable (which is also a valid solution).