Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

### 2019-03-11

posted Mar 11, 2019, 6:11 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: This method should modify the array, not return a new array.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. LAB - you should be able to complete this if you tested your partition method. We will expand on it tomorrow.make a git repo MKS22X-Quick and add a file to it: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: `/*return the value that is the kth smallest value of the array. `` */`` public static int quickselect(int []data, int k){ }`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 23-Test your method on different sized arrays. Don't just try big gaps like 10, 50, 100, your code might break for specific sizes!-This should work VERY fast for large arrays, provided you have few duplicates. -Try making a random array of 1's and 0's and watch the speed decrease! (on larger arrays)