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

2018-03-13

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

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. 


Comments