Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement