Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

### 2018-03-13

posted Mar 13, 2018, 10:07 AM by Konstantinovich Samuel
 Goal: QuickselectArray functions that work on an array "in place" will operate on the given array, and not make a copy, or use extra array space. This is often faster than re-copying the data.You should have a partition method. You should have tested itIMPORTANT: if you did not write this method in place, that is fine, but you will want to fix that after you get the rest of the code working. Regarding partition:What does this function do?How can you test this so you can easily verify it is working?hint: Visually easy to look at arrays will be your friend:{999,999,999,4,1,0,3,2,999,999,999}NOTE: I tested my code incorrectly and spent 30 minutes fixing a something that wasn't broken. NOW HW05 - you should be able to complete this if you tested your partition method. We will expand on it tomorrow.make a git directory and add a file to it:/05/Quick.javaWe discussed an algorithm where we find the Kth smallest element of an array. This is known as the quickselect function.Use your working and thoroughly tested partition method to write a Kth element selector function: public static int quickselect(int []data, int k){  //return the value that is the kth smallest value of the array.   //use your partition method to help you accomplish this.}int[]ary = { 2, 10, 15, 23, 0,  5};  //sorted :  {0,2,5,10,15,23}select( ary , 0 ) would return 0select( ary , 1 )  would return 2select( ary , 2 )  would return 5select( ary , 3 )  would return 10select( ary , 4 )  would return 15select( ary , 5 )  would return 23Test your method on different sized arrays.