do it in java A selection problem is a problem to find the kth order static elem
ID: 3693609 • Letter: D
Question
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 O(n). Use median-of-medians for choosing the pivot for partitioning Implement the selection algorithm using an object oriented programming language. Your code should be readable and well designed with a strategy pattern. including the following: - Readable, well designed program code (add comment for clarification) - the expected selection algorithm running timeExplanation / Answer
Algorithm step by step as follows
1.Take ArrayList length n.
2.Divide it list in to two
3. Using conditional statements add if Value smaller than pivot should go to smallerNumberList,if Value greater than pivot should go to greaterNumberList or nothing if value which is equal to pivot.
public int quickSelect(ArrayList<Integer>list, int nthSmallest)
{
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++)
{
if(list.get(i)<pivot)
{
smallerNumberList.add(list.get(i));
}
else (list.get(i)>pivot)
{
greaterNumberList.add(list.get(i));
}
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size())
{
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in //this list
else if(nthSmallest > (list.size() - greaterNumberList.size()))
{
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else
{
return pivot;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.