This is the code i need the table and graph if the array size is 1 then 2 then 3 then 4 the 5

- Your Statistics ( ArraySize-execution time ) table and graph

- Compare your results with the expected selection algorithm running time

import java.util.HashSet;

import java.util.Scanner;

public class Median

{

//BSelect by Blum, Floyd, Pratt, Rivest, Tarjon (1972)

//@Author Kishore Ravindran

//@Date of Creating 21-Feb-2011

//Algorithm: DeterministicSelect

//Step 1: Break n elements into blocks of 5 each.

//Step 2: Compute the median of each 5-element block in constant time.

//Step 3: Collect together the n/5 medians and recursively compute their median.

//Step 4: Chose the resulting element as a pivot

public static void main (String[] args)

{

System.out.println("Please enter the size of the array");

Scanner myscan = new Scanner(System.in);

// Handle InputMismatchException exception here;

int number = myscan.nextInt();

Integer [] input = new Integer[number];

System.out.println("Please enter the array elements");

System.out.println("");

for(int i=0;i

{

input[i] = myscan.nextInt();

}

System.out.println("Enter a number less than the size of the array");

System.out.println("");

// Check and InputMismatchException exception needs to be handled here;

number = myscan.nextInt();

Median m = new Median();

System.out.println("The " + number + "th smallest element in the input is " + m.DeterministicSelect(input, number));

}

// simple module to find the median of a array

int median(Integer[] array)

{

if (array.length == 1)

{

return array[0];

}

int smallerCount = 0;

for (int i = 0 ; i

{

for (int j = 0 ; j

{

if (array[i]

{

smallerCount++;

}

}

if (smallerCount == (array.length - 1)/2)

{

return array[i];

}

smallerCount = 0;

}

return -1; //should never happen

}

// finds pivot element of a given array recursively using DeterministicSelect

int Pivot(Integer[] array)

{

if (array.length == 1)

{

return array[0];

}

//Divide A into n/5 groups of 5 elements each

int numGroups = array.length / 5;

if (array.length % 5 > 0)

{

numGroups++;

}

Integer[] setOfMedians = new Integer[numGroups];

for (int i = 0 ; i

{

Integer[] subset;

if(array.length % 5 > 0)

{

if (i == numGroups - 1)

{

subset = new Integer[array.length % 5];

}

else

{

subset = new Integer[5];

}

}

else

{

subset = new Integer[5];

}

for (int j = 0; j

{

subset[j] = array[5*i+j];

}

//Find the median of each group

setOfMedians[i] = median(subset);

}

//Use DeterministicSelect to find the median, p, of the n/5 medians

int goodPivot = DeterministicSelect(setOfMedians, setOfMedians.length/2 );

return goodPivot;

}

//The algorithm in words:

//1. Divide n elements into groups of 5

//2. Find median of each group (How? How long?)

//3. Use Select() recursively to find median x of the n/5? medians

//4. Partition the n elements around x. Let k = rank(x)

//5. if (i == k) then return x else (i > k) use Select() recursively to find (i-k)th

//smallest element in last partition

//source

//Lecture PDF mentioned in the blog post

//and MIT Lecture 6 order statistics.

int DeterministicSelect(Integer[] array, int k)

{

if (array.length == 1)

{

return array[0];

}

int pivot = Pivot(array);

//set is used to ignore duplicate values

HashSet A1 = new HashSet();

HashSet A2 = new HashSet();

for (int i = 0; i

{

if (array[i]

{

A1.add(array[i]);

}

else if (array[i] > pivot)

{

A2.add(array[i]);

}

}

if (A1.size() >= k)

{

return DeterministicSelect(A1.toArray(new Integer[0]) ,k);

}

else if (A1.size() == k-1)

{

return pivot;

}

else

{

return DeterministicSelect(A2.toArray(new Integer[0]) , k - A1.size() - 1);

}

}

}