Basically I've spent several hours researching the best way to implement both a recursive and multi-threaded quick-sort and merge sort (this post is only about quick-sort). My goal in this is to take every logical processor in a given computer and pin them all for maximum quick-sort speed.
I took the approach of dividing up my problem recursively while creating threads until either the array was sorted or I hit the amount of processors on the cpu, in which case the rest of the problem would not be divided onto new threads but the remainder executed on their own core.
After creating a very rudimentary solution which could only work on my computer I ran into the Fork/Join framework which I tried to use below but I have literally no idea how. What I came up with was slower at sorting 10000000 random numbers ranging from 0 - 1000 than its single threaded counterpart, but I still think its interesting because in its docs it says, its able to steal work from slower threads whatever that means.
Then I just recently heard about thread pools and creating all of my threads initially and handing them out because creating new threads is taxing on the system. But I never got as far as trying to implement this. Perhaps my understanding of Fork/Join is skewed and I was wondering if anyone can point me in the right direction or tell me what I'm doing wrong in my current program.
Below you'll find my attempt at a multi threaded quick sort and a single threaded quick sort which is what I'm trying to translate to my multi threaded one. Any help is appreciated. Cheers!.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class MultithreadedQuicksort {
public static void main(String[] args) {
List<Comparable> nums = new ArrayList<Comparable>();
Random rand = new Random();
for (int i=0; i<10000000; i++) {
nums.add(rand.nextInt(1000));
}
long start = System.currentTimeMillis();
Quicksort quickSort = new Quicksort(nums, 0, nums.size() -1);
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(quickSort);
long end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(nums.size());
}
}
class Quicksort extends RecursiveAction {
int first;
int last;
private List<Comparable> nums;
Comparable midValue;
int midIndex;
int low;
int high;
public Quicksort(List<Comparable> nums){
this.nums=nums;
this.low = 0;
this.high = nums.size() - 1;
}
public Quicksort(List<Comparable> nums, int first, int last) {
this.first = first;
this.last = last;
this.nums = nums;
this.low = first;
this.high = last;
this.midIndex = (first + last) / 2;
this.midValue = nums.get(midIndex);
}
@Override
protected void compute() {
split();
if (high > first)
invokeAll(new Quicksort(nums, first, high));
if (low < last)
invokeAll(new Quicksort(nums, low, last));
}
public void split() {
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(low, high);
low++;
high--;
}
}
}
public void swap(int index1, int index2)
{
Comparable temp;
temp = nums.get(index1);
nums.set(index1, nums.get(index2));
nums.set(index2, temp);
}
}
Single Threaded
public static void quickSort(List<Comparable> nums, int first, int last) {
int low = first;
int high = last;
int midIndex = (first + last) / 2;
Comparable midValue = nums.get(midIndex);
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(nums, low, high);
low++;
high--;
}
}
if (high > first)
quickSort(nums, first, high);
if (low < last)
quickSort(nums, low, last);
}
