Re: Parallel quicksort

In article <d7-dnea9C8TRInPWnZ2dnUVZ7o2dnZ2d@brightview.co.uk>,
 "Jon Harrop" <usenet@ffconsultancy.com> wrote:


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