Please do it in Java A selection problem is a problem to find the kth order stat
ID: 3693406 • Letter: P
Question
Please do it in Java
A selection problem is a problem to find the kth order static element from a set of n distinct numbers. Input: a set A of n distinct numbers (unsorted) and an integer k. Output: the element x which is larger than k-1 other elements in A. The presented selection algorithm depend on divide-and-conquer algorithm and the expected running time 0(n).The important part in this algorithm is choosing the pivot for partitioning (randomly or median-of-medians). Implement the selection algorithm (using both method of selecting the pivot) using an object oriented programming language. Your code should be readable and well designed with a strategy pattern. (read about a strategy pattern). Run your code multiple times with different size of Array A, display your results in x-y plane where: X is the Size of the array Y is the execution time Requirements: Reading sections 9.2 & 9.3 from text book Reading about the strategy pattern Submission: including the following: Readable, well designed program code (add comment for clarification) Your Statistics (ArraySize-execution time) table and graph Compare your results with the expected selection algorithm running timeExplanation / Answer
class Test
{
public static void main(String args[])
{
//call your Selection
int A[]={}; //Input your Array
int k=; // Input your kth value
selection(A,k);
}
}
public static int selection(int[] A, int k) {
int start = 0, end = A.length - 1;
while (start < end) {
int r = start, w = end;
int mid = A[(r + w) / 2];
while (r < w) {
if (A[r] >= mid) {
int tmp = A[w];
A[w] = A[r];
A[r] = tmp;
w--;
} else {
r++;
}
}
if (A[r] > mid)
r--;
if (k <= r) {
end = r;
} else {
start = r + 1;
}
}
return A[k];
}