import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
@SuppressWarnings("serial")
/**
* An implementation of multi-thread quicksort for int arrays.
*
* Requires Java 7's fork join framework.
*/
public class ParallelQuicksort extends RecursiveAction {
/**
* Main function for timing and testing
* @param args unused
*/
public static void main(String[] args) {
int size = 1000000000;
//Create a list of random ints
int[] sortThis = new int[size];
System.out.println("Making random list");
for (int i = 0; i < size; i++) {
sortThis[i] = random.nextInt();
}
//do the sort
System.out.println("Parallel Quicksort started");
long start = System.currentTimeMillis();
sort(sortThis);
long stop = System.currentTimeMillis();
System.out.println("Parallel Quicksort ended and took: "
+ (stop - start) / 1000F + "s");
//check that the list is sorted
for (int i = 1; i < size; i++) {
assert sortThis[i - 1] <= sortThis[i];
}
System.out.println("Sort confirmed");
//Test Collections.sort
System.out.println("Testing java's sequential sort");
System.out.println("Making random list");
for (int i = 0; i < size; i++) {
sortThis[i] = random.nextInt();
}
System.out.println("Java's sequential sort started");
start = System.currentTimeMillis();
Arrays.sort(sortThis);
stop = System.currentTimeMillis();
System.out.println("Java's sequential sort ended and took: "
+ (stop - start) / 1000F + "s");
}
/**
* Sort an int array using a parallel quicksort
* @param list array to be sorted, in-place
*/
public static void sort(int [] list) {
ParallelQuicksort myFJQuickSort = new ParallelQuicksort(list, 0, list.length - 1);
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(myFJQuickSort);
pool.shutdown();
}
private static final Random random = new Random(1);
private final static int _sThreshold = 20; //When to switch to insertion
private final int[] _list;
private final int _l;
private final int _r;
public ParallelQuicksort(int[] list, int l, int r) {
_list = list;
_l = l;
_r = r;
}
@Override
protected void compute() {
int len = _r - _l + 1;
if (len <= _sThreshold) { //recursion base case
//For small n an insertion sort is faster than QS
insertion(_list,_l,_r);
return;
}
//select a random pivot point
int p = _l + random.nextInt(len - 1);
int pValue = _list[p];
swap(_list, p, _r); //move pivot value to end of the list
int swapPos = _l;
for (int i = _l; i < _r; i++) { //walk the list
if (_list[i] < pValue) { //move values < pivot value to the
swap(_list, i, swapPos);//front of the list
swapPos++;
}
}
swap(_list, _r, swapPos); //move pivot value back to original spot
//recurse twice; once on list containing values < pivot and once on values >= pivot
invokeAll(
new ParallelQuicksort(_list, _l, swapPos - 1),
new ParallelQuicksort(_list, swapPos + 1, _r));
}
private static void swap(int[] list, int i1, int i2) {
int temp = list[i1];
list[i1] = list[i2];
list[i2] = temp;
}
public static void insertion(int[] list, int l, int r) {
for (int i = l + 1; i <= r; i++) { //walk the list
int insertPos = i;
int li = list[i];
//find where this number goes in the sorted list
while (insertPos > l && li < list[insertPos - 1]) {
insertPos--;
}
//copy everything up one spot
System.arraycopy(
list, insertPos,
list, insertPos + 1,
i - insertPos);
list[insertPos] = li; //put this value int correct spot
}
}
}