Implement the recursive k-th smallestfunction from the book. Your program will p
ID: 3612703 • Letter: I
Question
Implement the recursive k-th smallestfunction from the book. Your program will prompt the user withmessage "integer:", then read an integer. Repeat this 10 times, andput the numbers in an array of size 10. Then print "k:" and readthe value of k. Finally print the k-th smallest of the 10 numbers.If k=0, print the smallest of all. Some of the code you need is inthe book. Do the partition as follows. Declare a global array"scratch" of size 10. Write a function int partition(int A[], intf, int l), which partitions the segment A[f]...A[l] and returns thepivot index. Use A[f] as the pivot. Copy numbers smaller than thepivot to the scratch array, starting at scratch[f]. Then copy thepivot, then copy numbers greater than the pivot. Finally copy thenumbers from scratch[f] to scratch[l] back to A[f] to A[l], andreturn the position of the pivot. code: kSmall (k, an Array, first,pivotIndex-1) if k<pivotIndex-first + 1 if k= pivotIndex-first + 1 kSmall (k-(pivotIndex-first+1),anArray, pivotindex+1,last) if k>pivotIndex-first+1 Implement the recursive k-th smallestfunction from the book. Your program will prompt the user withmessage "integer:", then read an integer. Repeat this 10 times, andput the numbers in an array of size 10. Then print "k:" and readthe value of k. Finally print the k-th smallest of the 10 numbers.If k=0, print the smallest of all. Some of the code you need is inthe book. Do the partition as follows. Declare a global array"scratch" of size 10. Write a function int partition(int A[], intf, int l), which partitions the segment A[f]...A[l] and returns thepivot index. Use A[f] as the pivot. Copy numbers smaller than thepivot to the scratch array, starting at scratch[f]. Then copy thepivot, then copy numbers greater than the pivot. Finally copy thenumbers from scratch[f] to scratch[l] back to A[f] to A[l], andreturn the position of the pivot. code: kSmall (k, an Array, first,pivotIndex-1) if k<pivotIndex-first + 1 if k= pivotIndex-first + 1 kSmall (k-(pivotIndex-first+1),anArray, pivotindex+1,last) if k>pivotIndex-first+1Explanation / Answer
// globalvariableint[] scratch; public int partition(int[] a, int f, inti) { intpivot=a[f]; scratch=newint[a.length]; // divide numbers based on > or< int bot=f; inttop=i-1; for(int x=f+1; x<i;x++) { // add lower valuesfrom the bottom // add lower valuesfrom the bottom if(a(x)<pivot) { scratch[bot++]=a(x); } // add higher valuesfrom the top // add higher valuesfrom the top else { scratch[top--]=a(x); } } // insert pivot scratch[bot]=pivot; // both bot and top contain the position of the emptyspot in the array between values greater than the pivot and valuesless than the pivot //copy values back int j=0; for(int x=f; x<i;x++) { a[x]=scratch[x]; } } For your main() method(input) public static void main(String[]args) { Scanner kb=newScanner(in); int[] array=newint[10]; for(int x=0; x<10;x++) { out.print("integer:"); array[x]=kb.nextInt(); } out.print("k:"); intk=kb.nextInt(); }