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

Write a program that performs a simple n-body simulation, called "jumping leprechauns." this simulation involves n leprechauns, numberd 1 to n. it maintains a gold value g_i for each leprechaun i, which begins with each leprechaun starting out with a million dollars worth of gold, that is, g_i = 1000000 for each i = 1,. in addition, the simulation also maintains, for each leprachaun,i, a place on the horizon, which is represented as a double-precision floating point number, x_i. in each iteration of the simulation, the simulation processes the leprachauns in order. processing a leprachaun i during its iteration begins by computing a new place on the horizon for i, which is determined by the assignment: