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


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:

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:

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)