Find Median in unsorted array using Quickselect algorithm

Question

I'm programming this excercise in here:https://www.hackerrank.com/challenges/find-median. I'm using quickselect algorithm but not for sorting array. i'm using it for divide array and find medican. But my code still don't work exactly, at least sample test in website.

7
0 1 2 4 6 5 3

I'm trying to look for my problem but i can't find them out. My code return true result in some case. Ex:

7
0 6 3 5 2 4 1

here is my code:

/**
 * file FindMedian.java
 */
import java.util.Scanner;
class Number{
    int n;

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }
}
public class FindMedian {
    public static int partition(int[] a, int low, int high, int n){
        int i=low+1, j= high;
        while (true){
            while(a[i]<a[low]){
                i++;
                if (i==high) break;
            }
            while (a[j]>a[low]){
                j--;
                if (j==low) break;
            }
            if (i>=j)
                break;
            swap(a, i, j);
            i++;
            j--;
        }
        swap(a, low, j);
        return j;
    }
    public static void progress(int[] a, int low, int high,int n, Number i){
        if (low>=high)
            return;
        int j= partition(a, low, high, n);

        if (j==n){
            i.setN(j);
            return;
        }
        else
        if (j>n)
            progress(a, low, j-1, n, i);
        else if (j<n)
            progress(a, j+1, high, n, i);
    }
    public static void swap(int[] a, int i, int j){
        int temp= a[i];
        a[i]= a[j];
        a[j]= temp;
    }

    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int a[]= new int[sc.nextInt()];
        int n= (a.length-1)/2;
        for (int index=0; index< a.length; index++)
            a[index]= sc.nextInt();

        Number i= new Number();
        i.setN(-1);

        progress(a, 0, a.length-1, n, i);

        if (i.getN()!=-1)
            System.out.println(a[i.getN()]);
        else System.out.println("Can't find");
    }
}

plz help me. thank you in advance :)

Answer 1

I believe you need to get the kth position of the pivot and cross check if its at the same position as the median, by performing this "int k=j-low+1;" with respect from the variable low in the array. For example a value at the 2nd index will be the 3rd smallest element in the array.

Also for the second recursive call, since we know the median is on the right hand side of the pivot(which is at the kth position) we expect the result to be at the (n-k)th position of the right hand sided subarray

 public static int progress(int[] a, int low, int high,int n){
        if (low==high)
            return a[low];
        //partition array and return index of pivot
        int j= partition(a, low, high, n);

        //find the kth position of the pivot 
        int k=j-low+1;
        //if the kth position of the pivot is the same as the required ith smallest int return pivot.
        if (k==n){
            return a[j];
        }
        else
        if (n<k)
           return progress(a, low, j-1, n, i);
        else if (n>k)
            return progress(a, j+1, high, n-k, i);
    }

Another thing that will be wrong is this line in your main method:

int n= (a.length-1)/2; 

It should be changed to int n=(a.length+1)/2, since the median of an array with an odd number of elements is located at the (N+1)/2 point(N=a.length).For example for an array with 7 elements, the median is expected at the (7+1)/2=4th position.