Question

Create an array of 10,000 elements, use sorted, near sorted, and unsorted arrays. Implement find the kth smallest item in an array. Use the first item as the pivot. Compare sets of results using a static call counter. Reset counter before running another search. Create a Test drive to exhaustively test the program.

// Assume all values in S are unique.

kSmall(int [] S, int k): int (value of k-smallest element)

pivot = arbitrary element from S:  let’s use the first element.

S1 = < all elements from S less than pivot > // these two steps will require some thought

S2 = < all elements from S greater than pivot > //  and need to be implemented

if k <= S1.length

    return kSmall(S1, k)

else if k == S1.length + 1

    return pivot

else

    return kSmall(S2, k – S1.length – 1)

Answer 1

please give thumbs up, thanks

CODE:

/**
*
* @author VISHAL
*/
public class KthSmallest {
public static int kSmall(int[]S,int k)
{
int[] S1;
int []S2;
int greater=0;
int lesser=0;
int pivot=S[0];
for(int i=0; i<S.length;i++)
{
if(S[i]<pivot)
lesser++;
else if(S[i]>pivot)
greater++;
}
S1=new int[lesser];
S2=new int[greater];
int m=0,n=0;
for(int i=0; i<S.length; i++)
{
if(S[i]<pivot)
S1[m++]=S[i];
else if(S[i]>pivot)
S2[n++]=S[i];
}
if(k<=S1.length)
return kSmall(S1,k);
else if( k==S1.length+1)
return pivot;
else
return kSmall(S2,k-S1.length-1);
}
public static void main(String[]args)
{
int A[]={2,5,3,7,6,8,10,76,45};
System.out.println(kSmall(A,5));
}
}