This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: d_rock on Jun 14th, 2012  |  syntax: Java  |  size: 3.70 KB  |  views: 220  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data