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

2019-03-11

posted Mar 11, 2019, 6:11 AM by Konstantinovich Samuel
Goal: Quickselect

Array 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 it

IMPORTANT: 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.java

We 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 0
select( ary , 1 )  would return 2
select( ary , 2 )  would return 5
select( ary , 3 )  would return 10
select( ary , 4 )  would return 15
select( 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)





Comments