Implement Quick Select using the “Median of Medians in java in order to find the median.
//Following is the required Java program. The array used to demonstrate is 8,5,3,4,5,1,3,2,6,8,6 with k = 5
import java.util.Arrays;
public class Main {
public static void main(String[] args)
{
int[] arr =
{8,5,3,4,5,1,3,2,6,8,6};
int k=5;
System.out.println(kth_smallest_iteratively(arr,k,0,arr.length-1));
}
//returns median of 5 or less elements, uses
in-place bubble sort/very well can use other in-place sort
public static int med5(int[] arr, int start, int
end){
if(start==end)return
arr[start];
//sort elements
for(int
i=end;i>start;i--){
for(int j=start+1;j<=end;j++){
if(arr[j-1]>arr[j])
swap(arr,j,j-1);
}
}
//return median
return
arr[start+((end-start+1)>>1)];
}
//get value for median of median
public static int getMedianOfMedian(int[] arr,
int start, int end){
int n=end-start+1;
if(n<=5) return
med5(arr,start,end);//less than 5 elements
int numOfGroups = n/5 +
(n%5==0?0:1);
//below medians array
is allocated on each recurrsive call
//can be minimized by
passing it from client and reusing
int[] medians = new
int[numOfGroups];//one median for each subgroup
for(int
i=0;i<numOfGroups;i++){
int groupStart=i*5;
int groupEnd = Math.min(arr.length-1, i*5+5-1);//last group can
have less than 5 elements
medians[i]=med5(arr,groupStart,groupEnd);
}
return
getMedianOfMedian(medians,0,medians.length-1);
}
//partition finds an pivot and put at its
final place
private static int partition_lamuto_stable(int[]
arr, int start, int end){
int pivot =
getMedianOfMedian(arr,start,end);
int
higher=start;//starting index of higher elements than pivot
int lower=start;//start
index of lower elements than pivot
int
pivotIndex=start;//starting index of elemetns equal to pivot(dup
pivot)
int[] copy= new
int[end-start+1];
for(int
i=start,k=0;i<=end;i++){
if(arr[i]<=pivot)higher++;//count all smaller elements and pivot
elements
if(arr[i]<pivot)pivotIndex++;//count all smaller elements
copy[k++]=arr[i];//create copy
}
for(int
i=0;i<copy.length;i++){
int index;
if(copy[i]<pivot) index=lower++;
else if(copy[i]==pivot) index=pivotIndex++;
else index=higher++;
arr[index]=copy[i];
}
return lower;//index
of pivot
}
public static int
kth_smallest_iteratively(int[] arr, int k, int start, int
end){
int pivotIndex=-1;
while(true){
pivotIndex=partition_lamuto_stable(arr, start,end);
if(pivotIndex+1==k)return arr[pivotIndex];
else if(pivotIndex+1<k) start=pivotIndex+1;
else end= pivotIndex-1;
}
}
private static void swap(int[] arr, int
index1, int index2){
int
temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
}
Please refer to the screenshot of the code to understand the indentation of the code
Output:
Hope this helped. Please do upvote and if there are any queries please ask in comments section.
Implement Quick Select using the “Median of Medians in java in order to find the median.
Order Statistics: A. Given two sorted arrays X and Y of equal size n, use Quick-Select to find the median of all 2n elements in arrays X and Y. Can you improve Quick-Select by choosing better pivots at every step?(in java) B. Show some experiments of your improved Quick-Select with arrays of size n=50. You can assume, if you want, that all the elements in the two arrays are distinct.
Implement the following sorting algorithms using Java: a. Heap Sort. b. Quick Sort. c. Radix Sort. Verify the correctness of each implemented algorithm by sorting the following array: 10, 5, 60, 53, 45, 3, 25,37,39,48
JAVA For the code in which I implemented most of the quick select algorithm. Quick select is a O(n) time algorithm to find the nth smallest value in an (unordered list). The following recursive algorithm finds thenth smallest element with an index bewtween left and right in list: Code: Integer QuickSelect(list, left, right, n) { if left = right // If we only have one index available return list[left] // return the element at that index endif pivotIndex ⇐ partition(list,...
Create a java code that will take user input and find the median using two heaps (max and min heap). The two heap must sort the elements from small to large. Running time must be efficient and below O(n^2). The algorithm must support the following methods: - insert(b): insert a given element b in O(logn) time - getMedian(): return the median in O(1) time - removeMedian(): remove and return the median in O(logn) time Note: The median will return the...
Java Write a pseudocode and Java program to implement the Stack using arrays. Write Push(), Pop(),and Display() methods to demonstrate that it works.
1. Write a Java program to implement Counting Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 2. Write a Java program to implement Bucket Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 3. In...
Information for Questions 3 and 4: In order to measure the effectiveness of their exercise plans, physical therapists collect data on their patients. Here are sets of three measurements of Left Hand Strength along with three measures of Right Hand Strength. The 6 measurements are taken on each day that the patient has physical therapy. The following data is for 10 different days. Right Hand Strength Median: Left Hand Median: Right Hand Day: 1 72 60 68 3 76 Left...
Use the algorithms SELECT, PARTITION, and CHOOSEPIVOTELEMENT to find the 6th smallest element of A = [12, 92, 64, 68, 54, 37, 57, 95, 56, 91, 32, 1, 30, 14, 35, 49, 66, 59, 76, 58). Show the results of each step of SELECT, PARTITION, and CHOOSEPIVOTELEMENT. You do not need to show the results of the recursive calls to SELECT to find the median of medians; for those calls, just show what the call would be and what the...
Using Java, Implement the size( ) method for the DoublyLinkedList class, assuming that we did not keep the size variable as an instance variable.
(20 points) Recall the following deterministic select algorithm:
(a) Divide the n elements into groups of size 5. So n/5 groups. (b)
Find the median of each group. (c) Find the median x of the n/5
medians by a recursive call to Select. (d) Call Partition with x as
the pivot. (e) Make a recursive call to Select either on the
smaller elements or larger elements (de- pending on the situation);
if the pivot is the answer we are done....