View difference between Paste ID: AcGvRGrA and 8eUbKX8P
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
}