medians of medians algorithm, implementation issues?

medians of medians algorithm, implementation issues?

As a part of median of median algorithm, I have to partition an array
based on a given element of the array. Please find the entire code below.
I am having some issues with the code as it doesn't give the correct
answer for say args[0] = 5/9 etc. I suspect a problem in the partition
method. Also, the algorithm says that making groups of 5 as long as u
don;t reach a size <= 5 and then pick the median of the array. I
understand that, that is not the true median. Correct ? and to find the
true median we must supply length/2 -1 as an input to the select method. ?
import java.util.Scanner;
import java.util.Arrays;
import java.util.Set;
import java.util.HashMap;
public class median_of_medians
{
private static HashMap<Integer, Integer> uiq; //<Key-actualNumberStored,
Value-index/position>
public static void main(String args[])
{
/*
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of elements:");
int num = scan.nextInt();
int inp[ ] = new int[num];
int i = 0;
while ( scan.hasNext() )
inp[i++] = scan.nextInt();
System.out.println(Arrays.toString(inp));
//System.out.println(select(inp, Integer.parseInt(args[0])));
*/
int arr[] = {5, 68, 10, 11, 13, 19, 55, 4, 3, 6, 8, 99, 101, 54, 58,
43, 27, 87, 63, 59, 20, 7, 2, 1, 22};
/*
int in = Integer.parseInt(args[0]);
if ( !uiq.contains(in) )
{
System.out.println("Wrong Pivot");
return;
}
System.out.println(partition({5, 1, 10, 6, 2, 7, 8, 4, 3}, 4));
System.out.println(findMedian(arr));
System.out.println(Arrays.toString(arr));
System.out.println(medianOfmedians(arr));
*/
System.out.println(select(arr, Integer.parseInt(args[0])));
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static int select( int arr[], int i)
{
//divide the arr into groups of 5 elements each
if ( arr.length <= 2 )
return arr[0];
int x = medianOfmedians(arr);
System.out.println("Partition about: " + x);
int k = partition(arr, x);
System.out.println(Arrays.toString(arr));
System.out.println("Positin returned: " + k);
if ( k == i )
return x;
else if ( i < k ) //copyrange excludes the end point so use
arr.length
return select( Arrays.copyOfRange(arr, 0, k), i );
else
return select( Arrays.copyOfRange(arr, k+1, arr.length), i-k -1);
}
//partition with the given element as the pivot
private static int partition(int arr[], int pivot)
{
createSet(arr);
int pos = uiq.get(pivot);
swap(arr, 0, pos);
int i = 0;
int j = arr.length-1;
while ( true )
{
while ( arr[i] <= arr[0] ) { i++; if ( i >= arr.length ) break ; }
while ( arr[j] > arr[0] ) j--;
if ( i >= j ) break;
swap(arr, i, j);
i++;
j--;
}
//we need to swap the pivot into its correct position
System.out.println(pos);
swap(arr, j, 0);
uiq.clear();
return j;
}
private static void swap(int []arr, int i, int j)
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
//input must be a non-empty array
private static int findMedian(int arr[])
{
System.out.println("The arr: " + Arrays.toString(arr));
if ( arr.length == 1 ) return arr[0];
//use insertion sort to first sort the array
int t;
int end = arr.length-1;
for ( int i = 1; i <= end ; i++ )
{
int j = i;
while ( j > 0 && arr[j] < arr[j-1] )
{
swap(arr, j, j-1);
j--;
}
}
return arr[(arr.length-1)/2];
}
private static int medianOfmedians(int arr[])
{
if ( arr.length == 0 ) return -1;
else if ( arr.length <= 5 ) return findMedian(arr);//i.e. call
insertion sort and directly return the median
else
{
int medians[] = new int[(arr.length+4)/5]; //a better way to
perform ceil
int s = 0, e;
while ( s < arr.length )
{
e = s + 5;
if ( e > arr.length ) e = arr.length;
medians[s/5] = findMedian(Arrays.copyOfRange(arr, s, e));
s = s + 5;
}
System.out.println("Loop complete.");
System.out.println(Arrays.toString(medians));
return medianOfmedians (medians);
}
}
private static void createSet(int arr[])
{
uiq = new HashMap<Integer, Integer>();
for ( int i = 0 ; i < arr.length ; i++ ) uiq.put(arr[i], i);
}
}