Finding median of 3 elements in array, and sorting them

Question

The method medianOfThree

1. returns the median of the first, center and last element in array
2. sorts the first, center, and last element of the array, so they are in order EXCEPT places the center in the second to last position.

Examples:

INPUT: 1,2,3
RETURN:2
EFFECT:1,2,3

INPUT: 3,2,1
RETURN:2
EFFECT:1,2,3

INPUT: 2,3,1
RETURN:2
EFFECT:1,2,3

INPUT: -2,-3,-8,1,20
RETURN:-2
EFFECT:-8,-3,1,-2,20

INPUT: 15,20,5,10
RETURN:15
EFFECT:10,5,15,20

NOTE: when the center is moved to the second to last position, it doesn't matter where the value that was previously there goes (as long as it's still in the array). Though this probably isn't relevant. In fact, as long as the first, last and one before last are in the correct place, the rest of the elements can get scrambled.

Here is the code. I tested it, but since it is rather complex it was hard to test (need to check return value and array and think carefully of expected result). Any suggestions for tools that make testing code like this easier?

/*
*Sorts first, center and last element, swaps the new center element with the one before the new last and returns its value.
*/
public static int medianOfThree(int[] sample, int start, int end) {
    if(sample.length < 3) {
        throw new IllegalArgumentException("arrays of length three or greater");
    }

    int center = (int)Math.floor((end-start)/2);

    if(sample[start] > sample[end])
       swap(sample, start, end);

    if(sample[start] > sample[center])
       swap(sample, start, center);

    if(sample[center] > sample[end])
       swap(sample, center, end);

int secondLast = end - 1

    swap(sample, center, secondLast );

    return sample[secondLast];

}

//swaps two elements in array given their positions
private static void swap(int[] sample, int x, int y) {
    int temp = sample[x];
    sample[x] = sample[y];
    sample[y] = temp;
}

Answer 1

Bug when finding center

Your code for finding the center is wrong:

int center = (int)Math.floor((end-start)/2);

For example, if start is 10 and end is 20, your calculation makes center be 5 when it should be 15. Also, you don't need Math.floor because you are using integer arithmetic so there is nothing to round up or down. You should change your code to this:

int center = start + (end-start)/2;

Answer 2

You seem to specify that it will only be 3 elements in the title of the question, but your input shows you input more than 3 every so often. Your sorting "algorithm" (a lot of swaps) is quite naïve in that sense - for examples of some sorting algorithms that you could implement, take a look at Wikipedia's article on Sorting Algorithms. No need to understand all of them - some get quite complex!

However, you don't have to write a sorting algorithm yourself to use one! Java has some built in for you.

import java.util.Arrays; // or java.util.Collections if you are using ArrayList etc
Arrays.sort(my_array); // this will sort your array for you, using the Quicksort algorithm

As @JS1 mentioned, your formula for finding the center is wrong, and should be

int center = start + (end - start) / 2;

And with that, you can simply return the center index of the array, since it's all sorted now!

public static int medianOfThree(int[] sample, int start, int end) {
    Arrays.sort(sample);
    return sample[start + (end - start) / 2];
}

...Unless the array has a length that is an even number. Then the median formula is a little different:

public static int medianOfFour(int[] sample, int start, int end) {
    Arrays.sort(sample);
    int medianRightIndex = start + (end - start) / 2;
    int medianLeftIndex = medianRightIndex - 1;
    return (sample[medianRightIndex] + sample[medianLeftIndex]) / 2;
}

However, unless you are specifying a range in the array (e.g. you only wanted the median of the first 3 elements), you don't need to specify the start and end parameters at all. start can be 0 and end can be sample.length. Again, this is only if you want the median of the entire array. For a specific subset, you'd still use start and end parameters.

Now we have arrived to:

public static int median(int[] sample) {
    Arrays.sort(sample);
    int median = 0;
    int index = sample.length / 2;
    if(sample.length % 2 == 0) {
        median = (sample[index] - sample[index - 1]) / 2;
    } else {
        median = sample[index];
    }
    return median;
}