package sorts;
import java.util.concurrent.RecursiveAction;
/**
* FJQuickSort_Partial.java
* Here is a partial implementation that may help you implement FJQuickSort_MINE.
*
*/
public class FJQuickSort_Partial extends GenericSortAlgorithm {
// Secondary array used by the algorithm.
private int[] other;
// Flag indicating which array currently holds the subarray to be sorted.
// If true, then "array" (from GenericSortAlgorithm) is the destination.
// If false, then "other" is the destination.
private boolean AIsArray;
// Cutoff threshold for using sequential sorting.
private static final int QS_CUTOFF = 10000;
private static final int PART_CUTOFF = 50000;
// Default constructor.
public FJQuickSort_Partial() {
}
// Constructor used for recursive tasks.
public FJQuickSort_Partial(int[] primary, int[] other, int left, int right, boolean aIsDest) {
super(primary, left, right);
// THIS bug took a long time!
if (aIsDest) {
this.array = primary;
this.other = other;
} else {
this.array = other;
this.other = primary;
}
this.AIsArray = aIsDest;
}
@Override
public String getName() {
return "FJQS Mine";
}
/**
* Overridden sort method. Allocates the secondary array and then invokes the sort.
*/
@Override
public void sort(int[] array) {
int n = array.length;
this.array = array;
this.other = new int[n];
this.left = 0;
this.right = n - 1;
this.AIsArray = true;
// Use the common pool.
pool.invoke(this);
}
/**
* This is the main compute method for the Fork�Join task.
* We treat the subarray as [left, right] (inclusive).
*/
@Override
protected void compute() { // looks good
// Set local variables for source and destination arrays.
// If primaryIsDestination is true, then array is the source and other is the destination;
// otherwise, other is the source and array is the destination.
int[] A, B;
if (AIsArray) {
A = array;
B = other;
} else {
A = other;
B = array;
}
if (right-left < QS_CUTOFF) {
// For small subarrays, simply sort sequentially.
quickSort(A, left, right); // Or call a better version!
// If the sorted output is not in the destination array, copy it.
if (!AIsArray) {
parallelCopy(A, B, left, right);
}
} else {
// For larger subarrays, perform the advanced partition.
int mid = left + (right - left) / 2;
swap(A, left, mid);
int pivotValue = A[left];
// Partition the subarray using our parallel prefix and pack.
// The partitionP method uses the interval [left, right+1) (right is exclusive).
Range pivots = partitionP(A, B, left, right + 1, pivotValue, AIsArray);
// Create recursive subtasks with swapped roles:
FJQuickSort_Partial leftTask = new FJQuickSort_Partial(B, A, left, pivots.lo - 1, !AIsArray);
FJQuickSort_Partial rightTask = new FJQuickSort_Partial(B, A, pivots.hi, right, !AIsArray);
leftTask.fork();
rightTask.compute();
leftTask.join();
}
}
/**
* Partition the subarray using a parallel prefix-sum and pack method.
* The interval is [l, r) (with r exclusive). Returns a Range object such that
* [Range.lo, Range.hi) are indices where pivotValue is placed.
*/
private Range partitionP(int[] in, int[] out, int l, int r, int pivotValue, boolean inIsDestination) { // looks good
// TODO Implement me as follows:
// Create a root note
// Call partition Up
// Call partition down (after doing a calculation based on result of partition up.
// Create a new Range object based on the results of parition up and down that
// contains the range of the pivots.
// Fill in the range with the pivot values
// return the range.
return null;
}
/**
* Parallel copy from one array to another in the interval [lo, r] (inclusive end).
*/
private void parallelCopy(int[] in, int[] out, int lo, int hi) { // looks good
if (hi - lo < PART_CUTOFF) {
for (int i = lo; i <= hi; i++) {
out[i] = in[i];
}
} else {
int mid = lo + (hi - lo) / 2;
ParallelCopyTask task1 = new ParallelCopyTask(in, out, lo, mid-1);
ParallelCopyTask task2 = new ParallelCopyTask(in, out, mid, hi);
task1.fork();
task2.compute();
task1.join();
}
}
private class ParallelCopyTask extends RecursiveAction { // looks good
int[] in, out;
int lo, hi;
ParallelCopyTask(int[] in, int[] out, int lo, int hi) {
this.in = in;
this.out = out;
this.lo = lo;
this.hi = hi;
}
@Override
protected void compute() {
parallelCopy(in, out, lo, hi);
}
}
/**
* Inner class to represent a range [lo, hi) (hi exclusive).
*/
private static class Range { // looks good
int lo, hi;
Range(int lo, int hi) { this.lo = lo; this.hi = hi; }
}
/**
* Inner class corresponding to the pnode structure.
* Represents a segment of the array and holds counts.
*/
private static class PNode { // looks good.
PNode left, right;
int sum, sum2; // Counts: sum = # of values < pivot, sum2 = # of values > pivot.
int lo, hi; // Interval [lo, hi) (hi exclusive)
int fl, fl2; // Prefix sums (fromLeft values)
PNode(int lo, int hi) {
this.lo = lo; this.hi = hi;
left = right = null;
sum = sum2 = fl = fl2 = 0;
}
}
/**
* Recursively compute counts for the node (partitionUp) in parallel.
*/
private static void partitionUp(PNode root, int[] in, int pivotValue) {
// TODO Implement me!
}
private static class PartitionUpTask extends RecursiveAction {
private final PNode node;
private final int[] in;
private final int pivotValue;
public PartitionUpTask(PNode node, int[] in, int pivotValue) {
this.node = node;
this.in = in;
this.pivotValue = pivotValue;
}
@Override
protected void compute() {
partitionUp(node, in, pivotValue);
}
}
/**
* Recursively propagate prefix sums and �pack� the elements (partitionDown) in parallel.
*/
private static void partitionDown(PNode root, int[] in, int[] out, int l, int l2, int pivotValue) {
// TODO Implement me!
}
private static class PartitionDownTask extends RecursiveAction {
private final PNode node;
private final int[] in, out;
private final int l, l2, pivotValue;
public PartitionDownTask(PNode node, int[] in, int[] out, int l, int l2, int pivotValue) {
this.node = node;
this.in = in;
this.out = out;
this.l = l;
this.l2 = l2;
this.pivotValue = pivotValue;
}
@Override
protected void compute() {
partitionDown(node, in, out, l, l2, pivotValue);
}
}
}