Recursive method using ArrayLists

Question

So I have this method which will take an ArrayList of Integers, I compare between 2 sub arrays and preform some swapping of numbers.

I am comparing the first elements of each sub array which is just the array halved, then swapping the elements if the bigger number isn't in the left subList. after that I want to recursively do the same thing but to the first half.

so if I type 3 5 8 2 1 7 6 4 I want to see this;

[3, 5, 8, 2, 1, 7, 6, 4]

[3, 7, 8, 4, 1, 5, 6, 2]

[8, 7, 3, 4, 1, 5, 6, 2]

What I want to be able to do is once I have done what I need to, to the base array, I need to work on the first half of the same array recursively. However when I compile, I get an error saying that I have incompatible types. So I'm assuming the subList function isn't providing me a ArrayList.

Any pointers on gettign this to work correctly?

public static void tournament(ArrayList<Integer> players){
int mid = players.size()/2;
    for(int i=0; i < mid; i++){
        if(players.subList(0,mid).get(i) < players.subList(mid,players.size()).get(i)){
            int temp = players.subList(0,mid).get(i);       
            players.subList(0,mid).set(i , players.subList(mid,players.size()).get(i));
            players.subList(mid,players.size()).set(i,temp);    
        }// end if
    }// end for
    System.out.println(players);

    if(players.size() > 2){
        tournament(players);
    }// end if

}// end tournament

I don't totally understand what you're trying to do, but some parts of your code seem needlessly convoluted. For example, players.subList(0,mid).get(i) is equivalent to players.get(i); and players.subList(mid,players.size()).set(i,temp) is equivalent to players.set(mid + i, temp). No? In fact, I don't see a single place where your use of subList is accomplishing anything. Also, your recursive call to tournament(players) doesn't really make sense, since that will recurse indefinitely (until you get a StackOverflowException). — ruakh
– ruakh, Commented Mar 31, 2012 at 3:43

Codie Westphall · Accepted Answer · 2012-04-01 01:42:59Z

Okay so with the help of a little cleaning up from ruakh I have got it working correctly. Greg Kopff was correct in that I couldn't return the subList as it was an incompatible type, So what I have done is pass two int elements into the method too.

These keep track of where the sub arrays would begin and progressively work their way closer through recursion.

public static void tournament(ArrayList<Integer> players, int left, int right){
    for(int i=0; i < right; i++){
        if(players.get(i) < players.get(right + i)){
            int temp = players.get(i);      
            players.set(i , players.get(right + i));
            players.set(right + i,temp);    
        }// end if
    }// end for

    right /= 2;
    System.out.println(players);
    if(right>=1){
        tournament(players,0,right);
    }
}// end tournament

Thanks for the help, this is a bit of homework, more personal homework so thanks for adding the tag, I didn't realize, nor did I expect people to give me the correct answer, just a guide as I knew I had to complete this with what I had learned so far. Thanks all for the help!

Greg Kopff · Accepted Answer · 2012-03-31 04:14:04Z

However when I compile, I get an error saying that I have incompatible types. So I'm assuming the subList function isn't providing me a ArrayList.

With the Collections API (of which the ArrayList is part), the best-practice is to declare your variables using the generic interfaces: List, Set, Map, rather than their concrete implementations such as ArrayList, HashSet and HashMap.

For example, instead of this:

ArrayList<Integer> list = new ArrayList<Integer>();

you should do this:

List<Integer> list = new ArrayList<Integer>();

If you take a look at the JavaDoc for java.util.List.subList(), you'll see that the method signature is this:

List<E> subList(int fromIndex, int toIndex)

ArrayList, as an implementation of the List interface, uses this exact same signature. Note that the return type is List, and not ArrayList. What this means is that ArrayList.subList() doesn't have to return you an ArrayList (although it could) - it simply has to return you an object that conforms to the List interface.

So what is the first step? Change your method to accept a List rather than an ArrayList. (Whatever method calls your tournament() initially method can still pass an ArrayList.)

public static void tournament(List<Integer> players)

Collectives™ on Stack Overflow

Recursive method using ArrayLists

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related