0

I have a problem with my Java code... I've been staring at it for over 10 hours now and I am just not able to find the mistake(s) I made.

My task was to implement the "median of medians"-algorithm, by splitting an array into arrays of maximum length 5 and look for their median. Then you look up the median of these medians and split your main-array into two parts, one with the smaller values and one with the bigger values. By the length of these arrays, you can now decide in which array you have to look for what position and then repeat the algorithm or finish if both arrays have the same size.

But somehow in most cases, my algorithm is one or two positions away from the correct result. So I think, that there is a small mistake somewhere, probably just with the range of a loop or something like this. So e.g. I tested the array {0,1,2,3,4,5,6,7,8} so the median is 4, but my program responds with 3 as the result.

I am absolutely aware, that this is a whole lot of code and my question might be not exactly what StackOverflow is there for. Also in most cases, I don't prefer letting other people look over my code, but I am desperate because I am not able to somehow find the mistake(s) I made. So I would be really thankful if somebody of you guys could look over it from a neutral position and maybe give me a small hint why it is not working in the way it should.

Thanks a lot

import java.util.Arrays;

public class MedianSelector {
    /**
     * Computes and retrieves the lower median of the given array of pairwise
     * distinct numbers using the Median algorithm presented in the lecture.
     * 
     * @param numbers array with pairwise distinct numbers.
     * @return the lower median.
     * @throw IllegalArgumentException if the array is {@code null} or empty.
     */
    public static int lowerMedian(int[] numbers) {
        // look out for wrong input
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Input is not correct");
        }

        if (numbers.length == 1) {
            return numbers[0];
        }

        return getValueAtPosition(numbers, ((numbers.length + 1) / 2) - 1);
    }

    private static int getValueAtPosition(int[] numbers, int positionI) {

        // if the array is smaller then 6 elements
        // find median immediately
        if (numbers.length <= 5) {
            return smallArraySort(numbers);
        }

        // splitting the array into small arrays of maximum size 5
        int fields = 0;
        // checking if the array is split-able in only arrays of length 5
        // if not, then put the remaining values into an array of size <5
        if (numbers.length % 5 == 0) {
            fields = numbers.length / 5;
        } else {
            fields = numbers.length / 5 + 1;
        }
        // creating an array to hold all the smaller arrays
        int[][] splitted = new int[fields][];
        // filling the array with the smaller arrays if every smallArray has size 5
        if (numbers.length % 5 == 0) {
            for (int i = 0; i <= splitted.length - 1; i++) {
                int[] smallArray = new int[5];
                for (int j = i * 5; j < (i + 1) * 5; j++) {
                    smallArray[j % 5] = numbers[j];
                }
                splitted[i] = smallArray;
            }
        } else {
            // filling the array with the smallerArrays if the last array is smaller then 5
            for (int i = 0; i < splitted.length - 1; i++) {
                int[] smallArray = new int[5];
                for (int j = i * 5; j < (i + 1) * 5; j++) {
                    smallArray[j % 5] = numbers[j];
                }
                splitted[i] = smallArray;
            }
            int[] smallArray = new int[numbers.length % 5];
            for (int j = 0; j < numbers.length % 5; j++) {
                smallArray[j] = numbers[(numbers.length) - (numbers.length % 5) + j];
            }
            splitted[fields - 1] = smallArray;
        }

        // calculating the median of every small Arrays and writing them into a bigger
        // array
        int[] medianCollectorArray = new int[fields];
        for (int i = 0; i < splitted.length; i++) {
            medianCollectorArray[i] = smallArraySort(splitted[i]);
        }

        // calculating the median of the array of medians recursively
        int x = lowerMedian(medianCollectorArray);

        // counting the items that are smaller then the median
        int counterK = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] < x) {
                counterK++;
            }
        }

        // if the position of x is the position we are looking for, then we have found
        // the median
        if (counterK == positionI) {
            return x;

            // if the position we are looking for is left from x, we need to repeat the
            // algorithm in all elements, that are smaller then x and
            // find positionI there
        } else if (positionI < counterK) {
            int[] L1 = new int[counterK];
            int index = 0;
            for (int i = 0; i <= numbers.length - 1; i++) {
                if (numbers[i] < x) {
                    L1[index] = numbers[i];
                    index++;
                }
            }
            return getValueAtPosition(L1, positionI);
        } else {
            // if the position we are looking for is right from x, we need to repeat the
            // algorithm in all elements, that are bigger then x
            // and find (positionI - counterK +1) there
            int[] L2 = new int[numbers.length - (counterK + 1)];
            int index = 0;
            for (int i = 0; i <= numbers.length - 1; i++) {
                if (numbers[i] > x) {
                    L2[index] = numbers[i];
                    index++;
                }
            }
            return getValueAtPosition(L2, positionI - (counterK + 1));
        }
    }

    /**
     * This method calculates the median of an array with max. 5 elements.
     * 
     * @param array an array with maximum 5 elements
     * @return the median of this array
     */
    private static int smallArraySort(int[] array) {
        if (array == null || array.length > 5 || array.length <= 0) {
            throw new IllegalArgumentException("This array shall not be sorted by this method!");
        }

        // TODO: IMPLEMENT A SORTING ALGORITHM BY MYSELF

        // sorting the array an returning its median
        Arrays.sort(array);
        return array[(array.length - 1) / 2];
    }
}

2 Answers 2

0

I think that you dont have to use Integer for these kind of calculations , try using double instead

0

I think the problem is that you're ignoring positionI when the length of numbers is less than or equal to 5.

You have:

if (numbers.length <= 5) {
    return smallArraySort(numbers);
}

I believe this should be:

if (numbers.length <= 5) {
    Arrays.sort(numbers);
    return numbers[positionI];
}

With just this change your code seems to produce the right answer, at least in all the cases I tried.

Just a small quibble, but this line:

return getValueAtPosition(numbers, ((numbers.length + 1) / 2) - 1);

could be simplified to:

return getValueAtPosition(numbers, (numbers.length - 1) / 2 );
2
  • Thank you very much... For the arrays I need to test, the result was always correct. :)
    – Mr. Moose
    May 16, 2020 at 18:50
  • Hey, that's always good enough for me :) This is quite a tricky algorithm to implement, well done. One tip - I was able to trace the problem by adding some well-place print statements to see intermediate values. I find this is almost always the best way to debug an algorithm - better than using a debugger I would say as you get to see the overall pattern of execution. May 16, 2020 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.