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


posted Mar 13, 2018, 10:07 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: 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:

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:

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: 

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 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.