Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Re: Parallel quicksort

Reply
Thread Tools

Re: Parallel quicksort

 
 
Kevin McMurtrie
Guest
Posts: n/a
 
      05-15-2010
In article <(E-Mail Removed)>,
"Jon Harrop" <(E-Mail Removed)> 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
different threads.

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))
{
final Thread t = new Thread()
{
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[left] to a[right], 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[right]))
// find item on left to swap
; // a[right] acts as sentinel
while (less(a[right], 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[i] and a[j]
private static void exch(double[] a, int i, int j)
{
double swap = a[i];
a[i] = 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[i] = 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Parallel Quicksort 1.0 here... aminer C++ 0 08-18-2012 07:23 PM
Parallel Quicksort 1.0 is here. aminer C++ 1 08-17-2012 11:50 PM
Re: Parallel quicksort Arne Vajh°j Java 9 11-06-2010 04:18 AM
Parallel port control with USB->Parallel converter Soren Python 4 02-14-2008 03:18 PM
Parallel quicksort (MPI) simo C Programming 2 03-07-2007 07:25 PM



Advertisments