Advertisement
d_rock

Untitled

Jun 14th, 2012
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Arrays;
  2. import java.util.Random;
  3. import java.util.concurrent.ForkJoinPool;
  4. import java.util.concurrent.RecursiveAction;
  5.  
  6.  
  7. @SuppressWarnings("serial")
  8. /**
  9.  * An implementation of multi-thread quicksort for int arrays.
  10.  *  
  11.  * Requires Java 7's fork join framework.
  12.  */
  13. public class ParallelQuicksort extends RecursiveAction {
  14.    
  15.     /**
  16.      * Main function for timing and testing
  17.      * @param args unused
  18.      */
  19.     public static void main(String[] args) {
  20.         int size = 1000000000;
  21.         //Create a list of random ints
  22.         int[] sortThis = new int[size];
  23.         System.out.println("Making random list");
  24.         for (int i = 0; i < size; i++) {
  25.             sortThis[i] = random.nextInt();
  26.         }
  27.        
  28.         //do the sort
  29.         System.out.println("Parallel Quicksort started");
  30.         long start = System.currentTimeMillis();
  31.         sort(sortThis);
  32.         long stop = System.currentTimeMillis();
  33.         System.out.println("Parallel Quicksort ended and took: "
  34.                 + (stop - start) / 1000F + "s");
  35.        
  36.         //check that the list is sorted
  37.         for (int i = 1; i < size; i++) {
  38.             assert sortThis[i - 1] <= sortThis[i];
  39.         }
  40.         System.out.println("Sort confirmed");
  41.        
  42.         //Test Collections.sort  
  43.         System.out.println("Testing java's sequential sort");
  44.         System.out.println("Making random list");
  45.         for (int i = 0; i < size; i++) {
  46.             sortThis[i] = random.nextInt();
  47.         }
  48.        
  49.         System.out.println("Java's sequential sort started");
  50.         start = System.currentTimeMillis();
  51.         Arrays.sort(sortThis);
  52.         stop = System.currentTimeMillis();
  53.         System.out.println("Java's sequential sort ended and took: "
  54.                 + (stop - start) / 1000F + "s");
  55.     }
  56.    
  57.     /**
  58.      * Sort an int array using a parallel quicksort
  59.      * @param list array to be sorted, in-place
  60.      */
  61.     public static void sort(int [] list) {             
  62.         ParallelQuicksort myFJQuickSort = new ParallelQuicksort(list, 0, list.length - 1);
  63.         ForkJoinPool pool = new ForkJoinPool();
  64.         pool.invoke(myFJQuickSort);
  65.         pool.shutdown();           
  66.     }
  67.    
  68.     private static final Random random = new Random(1);
  69.     private final static int _sThreshold = 20; //When to switch to insertion
  70.     private final int[] _list;
  71.     private final int _l;
  72.     private final int _r;
  73.    
  74.     public ParallelQuicksort(int[] list, int l, int r) {
  75.         _list = list;
  76.         _l = l;
  77.         _r = r;
  78.     }
  79.  
  80.     @Override
  81.     protected void compute() {
  82.         int len = _r - _l + 1;
  83.         if (len <= _sThreshold) { //recursion base case
  84.             //For small n an insertion sort is faster than QS
  85.             insertion(_list,_l,_r);
  86.             return;
  87.         }
  88.         //select a random pivot point
  89.         int p = _l + random.nextInt(len - 1);
  90.         int pValue = _list[p];
  91.         swap(_list, p, _r); //move pivot value to end of the list
  92.         int swapPos = _l;
  93.         for (int i = _l; i < _r; i++) { //walk the list
  94.             if (_list[i] < pValue) {    //move values < pivot value to the
  95.                 swap(_list, i, swapPos);//front of the list
  96.                 swapPos++;
  97.             }
  98.         }
  99.         swap(_list, _r, swapPos); //move pivot value back to original spot
  100.        
  101.         //recurse twice; once on list containing values < pivot and once on values >= pivot
  102.         invokeAll(
  103.                 new ParallelQuicksort(_list, _l, swapPos - 1),
  104.                 new ParallelQuicksort(_list, swapPos + 1, _r));
  105.     }
  106.  
  107.     private static void swap(int[] list, int i1, int i2) {
  108.         int temp = list[i1];
  109.         list[i1] = list[i2];
  110.         list[i2] = temp;
  111.     }
  112.    
  113.     public static void insertion(int[] list, int l, int r) {
  114.  
  115.         for (int i = l + 1; i <= r; i++) { //walk the list
  116.  
  117.             int insertPos = i;
  118.             int li = list[i];
  119.             //find where this number goes in the sorted list
  120.             while (insertPos > l && li < list[insertPos - 1]) {
  121.                 insertPos--;
  122.             }
  123.             //copy everything up one spot
  124.             System.arraycopy(
  125.                     list, insertPos,
  126.                     list, insertPos + 1,
  127.                     i - insertPos);
  128.             list[insertPos] = li; //put this value int correct spot
  129.         }
  130.     }
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement