Function in java outputs different results when called multiple times

Question

I have a function called tournamentTreeKSelection which finds the K-th largest element in an array. The function takes three parameters, the array, the same array again and the value of K. The purpose of sending two copies of the array is so that during recursive calls, I can modify one copy of the array and still keep the original array I sent in during that call. Here is the code:

import java.util.ArrayList;
import java.util.Arrays;

public class TournamentTree {

public static int max(int a, int b) {
    return a > b ? a : b;
}

public static int[] toArray(ArrayList<Integer> list) {
    int[] arr = new int[list.size()];
    for(int i = 0; i < arr.length; ++i)
        arr[i] = list.get(i);

    return arr;
}

public static ArrayList<Integer> toList(int[] arr) {
    ArrayList<Integer> list = new ArrayList<>();
    for(int i : arr)
        list.add(i);

    return list;
}


public static int tournamentKSelection(int[] data, int[] data_copy, int k) {
    ArrayList<Integer> winners = new ArrayList<>();

    for(int i = 0; i < data.length; i += 2) {
        winners.add(max(data[i], data[i + 1]));
    }

    if(k > 1 && winners.size() == 1) {
        for(int i = 0; i < data_copy.length; i++)
            if(data_copy[i] == winners.get(0))
                data_copy[i] = -1;

        return tournamentKSelection(data_copy, data_copy, --k);
    }

    if(winners.size() % 2 == 1 && winners.size() != 1) winners.add(-1);

    if(winners.size() == 1) return winners.get(0);

    return tournamentKSelection(toArray(winners), data_copy, k);

}
}

Now I am going to test it :

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
       int[] arr = {9, 10, 8, 7, 6, 500, 4, 3, 2, 1};


       System.out.println(TournamentTree.tournamentKSelection(arr,arr,1));
       System.out.println(TournamentTree.tournamentKSelection(arr,arr,2));
       System.out.println(TournamentTree.tournamentKSelection(arr,arr,3));


}
}

This produces the following results:

500 // ok this is the first largest number
 10 // ok this is the second largest number
  8 // this is the fourth largest number, not the third

Now let me make the call to System.out.println(TournamentTree.tournamentKSelection(arr,arr,3)); alone without the call to k = 1 and k = 2

import java.util.Arrays;

public class Test {
public static void main(String[] args) {
int[] arr = {9, 10, 8, 7, 6, 500, 4, 3, 2, 1};


System.out.println(TournamentTree.tournamentKSelection(arr,arr,3));


}
}

Now this produces the correct result, which is 9. What's going on ? Individually, the result is correct but when I make previous calls to the same function first the subsequent results are wrong.

The only explanation I can think of at the moment is that something in my TournamentTree class is static that shouldn't be.

Any insight ?

"different results when called multiple times" - That's very annoying indeed! Try a pure language like haskell if you don't want that to be possible ;) — Chris Martin, Dec 06 '15 at 00:18

score 2 · Accepted Answer · edited May 23 '17 at 12:23

2

I think you should call your function in this way:

System.out.println(TournamentTree.tournamentKSelection(arr.clone(), arr.clone(), 1));

And I recommend also interesting thread about arrays and passing them to function:

Are arrays passed by value or passed by reference in Java?

edited May 23 '17 at 12:23

Community

1
1

answered Dec 06 '15 at 00:45

Matt

1,298
1
12
31

score 1 · Answer 2 · answered Dec 06 '15 at 00:16

1

In the call TournamentTree.tournamentKSelection(arr,arr,3), you are passing in the same array for both args, so even though you are not changing the array through the second argument, you are changing it by the first. Java uses pass by reference, not pass by value. To maintain the original, you have to make a copy and pass in each, like:

public static void main(String[] args) {
    int[] arr = {9, 10, 8, 7, 6, 500, 4, 3, 2, 1};
    int[] arr_copy = java.util.Arrays.copyOf(arr, arr.length);

    System.out.println(TournamentTree.tournamentKSelection(arr,arr_copy,3));
}

answered Dec 06 '15 at 00:16

DBug

2,502
1
12
25

OK, technically, it is pass by value, but internally, it's passing the pointer to array, not a copy of it. – DBug Dec 06 '15 at 00:22
This still doesn't work. I did the following: `for(int i = 1; i < 11; i++) System.out.println(TournamentTree.tournamentKSelection(arr,arr_copy,i);` produces 500, 10, 9, 7, 3, -1, -1, -1, -1, -1 – Mutating Algorithm Dec 06 '15 at 00:24
@DBug the spirit of your explanation is correct, but the statement "Java uses pass by reference, not pass by value" is plain wrong - check out the *thousands* of votes on answers on that question that all repeat the mantra "java is *always* pass-by-value". Your answer would be better off without that statement altogether. – CupawnTae Dec 06 '15 at 00:51

Function in java outputs different results when called multiple times

2 Answers2