Finding Median of Array with Selection Sort

Question

I'm trying to find the median from an unsorted array in Java. First, I need to use the selection sort technique to sort the array, and I cannot use any Java library methods for sorting (so no Arrays.sort(array)). Also, I cannot sort the entire array either. I can only sort as many elements as necessary to find the median of the array. I suppose for an even array, it would be just half of the elements plus one (then find the average of the last two elements), and for an odd array it would just be half of the elements (the last being the median).

So I'm not sure how to stop the selection sort at just the right time and find the median from the last element or two of the partly sorted array. Below is what I have so far.

import java.util.Arrays;

public class EfficientMedian
{
    public static void median(int[] values)
    {
        int i, j, temp;
        double median;

        //selection sort below
        for (i = 0; i < values.length - 1; i++)
        {
            for (j = i + 1; j < values.length; j++)
            {
                if (values[i] > values[j])
                {
                    temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }
        if (values.length % 2 == 0) //if the array is even
        {
            median = values[values.length/2]; //just a placeholder
        }
        else //if the array is odd
        {
            median = values[values.length/2];
        }
        System.out.println(Arrays.toString(values));
        System.out.println(median);
    }
    public static void main(String[] args)
    {
        int[] array1 = {567, 2, 600, 6, 601}, array2 = {45, 300, 46, 49};
        median(array1);
        median(array2);
    }
}

Answer 1

Your first loop selects elements to sort. If you only need median, you only need to sort values.length/2 elements. So you should edit this:

for (i = 0; i < values.length - 1; i++)
    {
        ...
    }

to

for (i = 0; i < values.length/2; i++)
    {
        ...
    }

and fyi in the "length of the array is odd" case, the convention is to average middle two values.