# Re: Parallel quicksort

Discussion in 'Java' started by Kevin McMurtrie, May 16, 2010.

1. ### Kevin McMurtrieGuest

In article <>,
"Jon Harrop" <> wrote:

> I cannot find an implementation of parallel quicksort in Java. Does anyone
> have one or know where I can get one?

This question came up before and I still have the code lying around.
It is not tuned and better algorithms exist. This only demonstrates
putting the left and right sub-sorts of an existing algorithm on

Quicksort is typically limited by memory throughput. Multithreading
helps when comparing values is computationally expensive. For a massively
parallel system you'd probably quicksort subsets on different hardware
then produce a single sorted stream through mergesort.

public class Run
{
/***************************************************************************
* Quicksort code from Sedgewick 7.1, 7.2.
**************************************************************************/
public static void quicksort(double[] a)
{
//shuffle(a); // to guard against worst-case
quicksort(a, 0, a.length - 1, 0);
}

static void quicksort(final double[] a, final int left, final int right, final int tdepth)
{
if (right <= left)
return;
final int i = partition(a, left, right);

if ((tdepth < 4) && ((i - left) > 1000))
{
{
public void run()
{
quicksort(a, left, i - 1, tdepth + 1);
}
};
t.start();
quicksort(a, i + 1, right, tdepth + 1);

try
{
t.join();
}
catch (InterruptedException e)
{
throw new RuntimeException("Cancelled", e);
}
} else
{
quicksort(a, left, i - 1, tdepth);
quicksort(a, i + 1, right, tdepth);
}
}

// partition a
to a
, assumes left < right
private static int partition(double[] a, int left, int right)
{
int i = left - 1;
int j = right;
while (true)
{
while (less(a[++i], a
))
// find item on left to swap
; // a
acts as sentinel
while (less(a
, a[--j]))
// find item on right to swap
if (j == left)
break; // don't go out-of-bounds
if (i >= j)
break; // check if pointers cross
exch(a, i, j); // swap two elements into place
}
exch(a, i, right); // swap with partition element
return i;
}

// is x < y ?
private static boolean less(double x, double y)
{
return (x < y);
}

// exchange a and a[j]
private static void exch(double[] a, int i, int j)
{
double swap = a;
a = a[j];
a[j] = swap;
}

// shuffle the array a[]
private static void shuffle(double[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int r = i + (int) (Math.random() * (N - i)); // between i and N-1
exch(a, i, r);
}
}

// test client
public static void main(String[] args)
{
int N = 5000000; // Integer.parseInt(args[0]);

// generate N random real numbers between 0 and 1
long start = System.currentTimeMillis();
double[] a = new double[N];
for (int i = 0; i < N; i++)
a = Math.random();
long stop = System.currentTimeMillis();
double elapsed = (stop - start) / 1000.0;
System.out.println("Generating input: " + elapsed + " seconds");

// sort them
start = System.currentTimeMillis();
quicksort(a);
stop = System.currentTimeMillis();
elapsed = (stop - start) / 1000.0;
System.out.println("Quicksort: " + elapsed + " seconds");

}
}
--
I won't see Google Groups replies because I must filter them as spam

Kevin McMurtrie, May 16, 2010