I am writing a program that is an altered version of the quick sort to find the median of a set of integers in an array. My first problem is that I have an index out of bounds error that I can't seem to get rid of. Secondly, I'm not sure how u would find the median of the array if the number of elements is even. The program searches based on the index and I don't know how I would go about finding the average of the two elements.
For input the first number is the number of elements, followed by the elements themselves.
3
0
5
4
So 4 should be returned.
Code:
import java.util.*;
public class randoSelect {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] array=new int[N];
int searchNum=0;
for(int i=0;i<N;i++)
{
array[i]=sc.nextInt();
}
if (N%2!=0)
{
searchNum=((N-1)/2)+1;
}
//System.out.println("searchnum="+searchNum);
int median = randomizedSelect(array, 0, array.length-1, searchNum);
System.out.println(median);
}
public static int randomizedSelect (int[] array,int p,int r, int i)
{
if (p==r)
return array[p];
int center = randomizedPartition(array, p, r);
int k = center-p+1;
if (k==i)
return array[center];
else if (i<k)
return randomizedSelect(array,p,center-1,i);
else
return randomizedSelect(array,center+1,r,i-k);
}
public static int randomizedPartition(int[] array, int begin, int end)
{
Random num=new Random();
int index=num.nextInt((end-begin)+1)+begin;
int pivot=array[index];
swap(array,array[index], array[end]);
index=end;
int i=begin-1;
for (int j=begin; j<=end-1;j++)
{
if (array[j]<=pivot)
{
i++;
swap(array,array[i],array[j]);
}
}
swap(array,array[i+1],array[index]);
return i+1;
}
public static void swap(int[] array, int index1, int index2)
{
int temp=array[index1];
array[index1]=array[index2];
array[index2]=temp;
}
}
Aucun commentaire:
Enregistrer un commentaire