Implement the two algorithms for finding the kth smallest integer in a set of integers using only one array that contains all the integers. Test your programs and compute the CPU time for different sets of integers generated by a random number generator.

Java preferred.

Algorithm 1:

Procedure SELECT( k,S)

{ if ISI =1 then return the single element in S

else { choose an element a randomly from S;

let S1,S2,and S3 be he sequences of elements in S

less than, equal to, and greater than m, respectively;

if IS1I >=k then return SELECT(k,S1)

else

if (IS1I + IS2I >=k then return m

else return SELECT(k-IS1I-IS2I , S3);

}

}

Algorithm 2:

Procedure SELECT(k,S)

{if ISI<50 then { sort S; return the kth smallest element;}

else

{ divide S into ISI/5 sequences of 5 elements each with up

to four leftover elements;

sort each 5-element sequence;

let M be the sequence of the medians of the 5-element sets;

let m= SELECT( M/2, M); // where M/2 indicates the //smallest integer greater than M/2

let S1,S2,and S3 be he sequences of elements in S

less than, equal to, and greater than m, respectively;

if IS1I >=k then return SELECT(k,S1)

else

if (IS1I + IS2I >=k then return m

else return SELECT(k-IS1I-IS2I , S3);

}