Re: Parallel quicksort

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

  1. 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
    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
    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
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. simo

    Parallel quicksort (MPI)

    simo, Mar 7, 2007, in forum: C Programming
    Replies:
    2
    Views:
    2,197
    user923005
    Mar 7, 2007
  2. Soren
    Replies:
    4
    Views:
    1,349
    c d saunter
    Feb 14, 2008
  3. Arne Vajhøj

    Re: Parallel quicksort

    Arne Vajhøj, May 16, 2010, in forum: Java
    Replies:
    9
    Views:
    1,413
    kebodi
    Nov 6, 2010
  4. aminer
    Replies:
    1
    Views:
    576
    aminer
    Aug 18, 2012
  5. aminer
    Replies:
    0
    Views:
    383
    aminer
    Aug 18, 2012
Loading...

Share This Page