SHOW:
|
|
- or go back to the newest paste.
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 | - | System.out.println("Parallel Quicksort ended and took: " + (stop - start) / 1000F + "s"); |
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: " + (stop - start) / 1000F + "s"); |
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 | - | if (_list[i] < pValue) { //move values < pivot value to the front of the list |
93 | + | |
94 | - | swap(_list, i, swapPos); |
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 | } |