Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-03-15 HW

posted Mar 14, 2017, 9:44 PM by Samuel Konstantinovich   [ updated Mar 14, 2017, 11:56 PM ]
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. Sometimes

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. 

public static int part ( int [] data, int start, int end){
    //-Choose a random element to be a pivot, and partition the array around it. 
    //-Only partition the elements from start to end inclusive.
    //-When done returns the index of the final position of the pivot element.      
    //    (Should be from start to end inclusive)

Regarding partition:
What does this function do?
How can you test this so you can easily verify it is working?
NOTE: I tested my code incorrectly and spent 30 minutes fixing a something that wasn't broken. 

hint: Visually easy to look at arrays will be your friend:

NOW HW07 - 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 last Friday, 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};
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.