Re: Parallel quicksort
On 15-05-2010 11:35, Jon Harrop wrote:
I cannot find an implementation of parallel quicksort in Java. Does
anyone have one or know where I can get one?
public static void tqsint(int[] ia, int tdepth) {
tqsint_help(0, ia.length - 1, ia, 0, tdepth);
return;
}
public static void tqsint_help(int n1, int n2, int[] ia, int depth,
int tdepth) {
int tmp;
int l = n1;
int r = n2;
int pivot = ia[(n1 + n2) / 2];
do {
while (ia[l] < pivot)
l++;
while (ia[r] > pivot)
r--;
if (l <= r) {
tmp = ia[l];
ia[l] = ia[r];
ia[r] = tmp;
l++;
r--;
}
} while (l <= r);
if (depth >= tdepth) {
if (n1 < r)
tqsint_help(n1, r, ia, depth + 1, tdepth);
if (l < n2)
tqsint_help(l, n2, ia, depth + 1, tdepth);
} else {
ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
tdepth);
ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
tdepth);
h1.start();
h2.start();
try {
h1.join();
h2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
return;
}
....
class ThreadSortHelp extends Thread {
private int n1;
private int n2;
private int[] ia;
private int depth;
private int tdepth;
public ThreadSortHelp(int n1, int n2, int[] ia, int depth, int tdepth) {
super();
this.n1 = n1;
this.n2 = n2;
this.ia = ia;
this.depth = depth;
this.tdepth = tdepth;
}
public void run() {
ThreadSort.tqsint_help(n1, n2, ia, depth, tdepth);
}
}
Arne