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: lets 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)