Slove the flowing Problem Description In this project, based on the discussion i

Question

Slove the flowing

Problem Description In this project, based on the discussion in Section 4.5(Text) you will implement the selection problem to find the kth smallest element in a list of n numbers, where k (1,n) (note that array indices are from 0..(n - 1)). The data will be held in a 1 dimensional array. You will implement the recursive version of this algorithm using the Hoare partition technique. Here, you will run your algorithm to find the median of the dataset for N = 8, 16, 32, 64, 128, 256, 512, 1024. As in previous projects use a random number generator to generate values in the range (0-4999). You will count the number of comparisons your algorithm takes for each run and print these out for for each N value. These will then be plotted. Use a median-of-three algorithm to choose the pivot to ensure even partitions. Implementation Details Your function prototype can be as follows: int Selection Recursive ( int A[], int kthSmallest, int sizeofA) Output: The following guidelines must be strictly followed for full credit: A single run of the application should produce all of the needed output. For N = 8, 16, print the original array and the reported median value Print a table of N vs. #Comparisons. Plot N vs. #Comparisons. Requirements: This project must be performed individually by you; you are not to use any other source code to help you solve the problem. Your primary source of reference is the text book. You are not to consult internet or any other sources for existing code; one important goal of this project is derive an implementation from the algorithm description and examples in the text book, thus assessing your understanding of the design concepts(decrease/conquer) and their application to this problem. No late credit; sources and output to be turned in via Module by the deadline. Source must compile on Woodward 335 lab machines. Sources and output must be well documented for full credit. K.R. Subramanian

Explanation / Answer

import java.util.Random;

import java.util.Scanner;

public class SelectionRecursiveAlgorithm

{

static int noOfComaparisons=0;

public static void main(String argv[])

{

Random r=new Random();

Scanner in=new Scanner(System.in);

System.out.println("enter the value of k");

int k=in.nextInt();

for(int i=8;i<=1024;i=i*2)

{

int a[]=new int[i];

for(int j=0;j<i;j++)

{

a[j]=r.nextInt(5000);

}

for(int j=0;j<i;j++)

System.out.print(a[j]+" ");

noOfComaparisons=0;

int num=SelectionRecursive(a,0,i-1,k);

System.out.println(" "+k+" th smallest= "+num);

System.out.println("total no Elements= "+i);

System.out.println("no of comaprisions performed= "+noOfComaparisons);

}

}

public static int SelectionRecursive(int a[],int left,int right,int k)

{

if(left==right)

return a[left];

int pivotIndex=right;

pivotIndex=partition(a,left,right,pivotIndex);

int pivotDistance=pivotIndex-left+1;

if(pivotDistance==k)

return a[pivotIndex];

else if(pivotDistance>k)

return SelectionRecursive(a,left,pivotIndex-1,k);

else

return SelectionRecursive(a,pivotIndex+1,right,k-pivotDistance);

}

public static int partition(int a[],int left,int right,int pivotIndex)

{

int storeIndex=left;

for(int i=left;i<right;i++)

{

noOfComaparisons++;

if(a[i]<a[right])

{

int temp=a[i];

a[i]=a[storeIndex];

a[storeIndex]=temp;

storeIndex++;

}

}

int temp=a[right];

a[right]=a[storeIndex];

a[storeIndex]=temp;

return storeIndex;

}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.