Implement the two algorithms for finding the kth smallest in

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);

}

Solution

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);

             }

}