Find largest array element with a Comparator in Java

Question

So I have an exam on Tuesday for Algorithms and Data but I can't solve this question from a past paper.

Write a Java static method called greatest which takes an array of objects and a Comparator object which can order objects of the array’s element type, and returns whichever element from that array is greatest according to the order given by the Comparator object. You may assume the array is of length at least 1. Your code must use no method from Java’s API except the method compare from type Comparator.Your method must be generic, so the array could have any non-primitive element type.

My Attempt:

public static void greatest(Object[] a, Comparator<Object> x) {
        for (int i = 0; i < a.length; i++) {
            x.compare(a[i], a[i+1]));
        }
    }

But as you can probably see I'm pretty clueless and I'm sure my attempt is wrong! Any help would be great. I have looked at comparator's online but they just seem to be for a specific data type whereas this is for any non-primitive element type.

Start with the algorithm only. Try finding the biggest int in an array of int. You'll need a variable holding the biggest int. Then apply the same algorithm to an array of comparable objects. — JB Nizet
– JB Nizet, Commented May 2, 2015 at 16:52
Frankly, I don't understand why your teacher asks you to deal with generic types, which are quite an advanced and complex matter, if you don't master variables, loops, and basic algorithmics yet. This is too complex for your current level. — JB Nizet
– JB Nizet, Commented May 2, 2015 at 17:03
Maybe the topic of the task is generics not looping? The knowledge level of the rest of the class might be different... — eckes
– eckes, Commented May 2, 2015 at 17:06

Martin M J · Accepted Answer · 2015-05-02 17:07:22Z

2

Compare<T> is a generic interface, as seen by the parameter <T>. T can be any class. Because the below method takes an argument of type Comparator<T>, it can take any comparator that implements this interface.

Note that the array holds objects of type T. This is necessary, because the Comparator only knows how to compare objects of this type.

public static <T> T greatest(T[] a, Comparator<? super T> x) {
    T greatest = a[0];
    for (int i = 1; i < a.length; i++) {
        if (x.compare(a[i], greatest) > 0) {
            greatest = a[i];
        }
    }
    return greatest;
}

edited May 2, 2015 at 17:07

answered May 2, 2015 at 16:53

Martin M J

8801 gold badge5 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

isnot2bad Over a year ago

Almost. Type parameter T is not declared and the method does not have a return type yet.

Martin M J Over a year ago

Ah, my bad. I forgot to add it after copying his method.

isnot2bad Over a year ago

Improvement: Use Comparator<? super T> so that any comparator that is able to compare objects of type T or any super-type of T is accepted.

Tesseract · Accepted Answer · 2015-05-02 17:01:26Z

1

Your method is supposed to be generic and return a result. Here is part of the solution, you just have to add a few things to make it complete.

public static <T> T greatest(T[] a, Comparator<? super T> comp) {
    T greatest = a[0];
    for(int i = 1; i < a.length; i++) {
    }
    return greatest;
}

edited May 2, 2015 at 17:01

answered May 2, 2015 at 16:52

Tesseract

8,1392 gold badges23 silver badges37 bronze badges

1 Comment

isnot2bad Over a year ago

You should use a bounded wildcard for the Comparator's type parameter, so a comparator for a super-type of T is accepted too.

Manuel Jain · Accepted Answer · 2015-05-02 16:55:34Z

1

initialize the current maximum with the first element a[0]
iterate over the array and compare the current element with the maximum
if current element is greater then maximum, it is the new maximum
return the maximum

answered May 2, 2015 at 16:55

Manuel Jain

7511 gold badge6 silver badges16 bronze badges

Comments

eckes · Accepted Answer · 2015-05-02 16:57:09Z

The method must be generic (in the text the "object" is used missleading). It also needs to return the result (in this case an object of the input type, but some solutions might instead return the index of the object).

So the function declaration will look like:

public static <T> T greatest(T[] objects, Comparator<T> comparator)

And then you need to find the biggest one. This is simply done by remembering the biggest one you have seen so far. As soon as a element was larger, remember the new one:

{
    assert objects.length >= 1;
    T pivot = objects[0]; // assume the first is biggest
    for(T o : objects) // no good way to start with second
    {
        if (comp.compare(o, pivot) > 0) // if o is bigger
            pivot = o;
    }
    return pivot;
}

The code is uncompiled and untested.

Anand Balakrishnan · Accepted Answer · 2015-05-02 22:19:58Z

0

Try this:

public static T greatest(T[] a, Comparator<T> x) {
    T temp = a[0];
    for (int i = 0; i < a.length;i++) {
        if (x.compare(temp,a[i]) <= 0) {
            temp = a[i];
        }
    }
    return temp;
}

edited May 2, 2015 at 22:19

answered May 2, 2015 at 17:01

Anand Balakrishnan

214 bronze badges

3 Comments

isnot2bad Over a year ago

I think for the OP the method declaration is important. And the method should be generic.

Anand Balakrishnan Over a year ago

So then change the Object to T. Simple. Hell, you could edit the answer isnot2bad!

isnot2bad Over a year ago

It's not my answer. It's your's. I'm not your tutor/ghost writer. I've downvoted it because it's not complete and its also wrong concerning the generic thing. Fix it and I'll revoke my downvote.

Collectives™ on Stack Overflow

Find largest array element with a Comparator in Java

5 Answers 5

3 Comments

1 Comment

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related