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

2019-03-12

posted Mar 12, 2019, 6:16 AM by Konstantinovich Samuel   [ updated Mar 13, 2019, 7:47 AM ]
Goal: Quicksort.

When trying write partition, you really need to draw a diagram with variable names, and see what your cases are.
Using the pivot (data[lo]) and the 2 not yet compared values (data[i] and data[j] )
Basic Partitioning:

private int partitionDutch(int[],int lo, int hi){
    //your code.
    return j;
}


Improvements for partition:
1. Easy ( Implement both of these)
    a - When choosing a pivot, use the median value of the lo,hi, and middle elements.
    b - When a data element is equal to the pivot, make a 50% chance that you swap it to the other side.
This prevents all the pivot values from ending up on one side of the pivot.
   
2. Harder - Extra credit
   Implement the dutch flag algorithm


Quicksort:
Assume you have partitioned your array once:
How many values does partition put into the correct sorted location after each pass?
How many times on average should the quickselect call partition?



What would happen if we parittioned BOTH sides instead of just one?

Remember that in this diagram each new row is just a visual aid, not a new array copy, since partition is in place.



LAB REQUIREMENTS: (Due Friday 8am)
2 more lab days (Tues/Wed)

Your repo: MKS22X-Quick

File: Quick.java
    
/*return the value that is the kth smallest value of the array. k=0 is the smallest
 */
 public static int quickselect(int[] data, int k)

/*Modify the array to be in increasing order.
 */  
 public static void quicksort(int[] data)


Things to do: (and the order that makes the most sense)
1-Complete and test partition.
2-Complete Quickselect using partition
3-Improve partition (minimally using the easy improvement below) and test quickselect on an array of duplicate values. Should not be significantly longer than all unique values.
4-Complete Quicksort.
5-Optionally implement dutch flag paritioning and update quicksort to include this.




extra credit: (skip this until you need it)


Dutch Flag Partitioning:
Your partition will return two values (lt, and gt), you can then decide which section to call partition again!

private int[] partitionDutch(int[],int lo, int hi){   
    //your code
    //return an array [lt,gt]
}

You will need to demonstrate that your dutch flag works in your quicksort for extra credit.


index:             lt              i                    gt           
        |-----------|--------------|---------------------|----------|
regions:      r1           r2               r3               r4

r1 are less than the pivot
r2 are equal to the pivot
r3 are UNKNOWN! 
r4 are greater than the pivot


Comments