Go up to Example Programs Go forward to Long Integer Multiplication

Quicksort

// ----------------------------------------------------------------------------
//
// qsort.cc
// Quicksort
//
// $Id: app_qsort.tex,v 1.1 1996/04/01 07:24:21 schreine Exp $
// (C) 1996 Wolfgang Schreiner <Wolfgang.Schreiner@risc.uni-linz.ac.at>
//
// ----------------------------------------------------------------------------

#include <rt++.h>

Atom(int);
Atom(float);
Ref(Array<float>);
ThreadRes(int);
ThreadArg3(A, int, Array<float>, int, int);

const int MIN = 1000;

// ----------------------------------------------------------------------------
//
// swap two values
//
// ----------------------------------------------------------------------------
static inline void swap(Array<float> a, int x, int y)
{
  float z = a[x];
  a[x] = a[y];
  a[y] = z;
}

// ----------------------------------------------------------------------------
//
// split <a/l/r> by pivot <e> into <a/l/x0> and <a/y0/r>
//
// ----------------------------------------------------------------------------
void split(Array<float> a, int l, int r, float e, int *x0, int *y0)
{
  int x = l;
  int y = r-1;
  do
    {
      while (a[x] < e) x++;
      while (a[y] > e) y--;
      if (x < y)
        {
          swap(a, x, y);
          x++; y--;
        }
      else if (x == y)
        {
          break;
        }
    }
  while (x <= y);
  *x0 = x; *y0 = y+1;
}

// ----------------------------------------------------------------------------
//
// sort <a/l/r> sequentially
//
// ----------------------------------------------------------------------------
int qs0(Array<float> a, int l, int r)
{
  if (l < r) 
    {
      float e = a[(l+r)/2];
      int m0, m1;
      split(a, l, r, e, &m0, &m1);
      qs0(a, l, m0);
      qs0(a, m1, r);
    }
  return(0);
}

// ----------------------------------------------------------------------------
//
// sort <a/l/r> in parallel
//
// ----------------------------------------------------------------------------
int qs(Array<float> a, int l, int r)
{
  if (r-l < MIN) return(qs0(a, l, r));
  float e = a[(l+r)/2];
  int m0, m1;
  split(a, l, r, e, &m0, &m1);
  Thread3 <int, Array<float>, int, int> t0(qs, a, l, m0);
  Thread3 <int, Array<float>, int, int> t1(qs, a, m1, r);
  Wait(t0);
  Wait(t1);
  return(0);
}

// ----------------------------------------------------------------------------
//
// sort <a>
//
// ----------------------------------------------------------------------------
void qsort(Array<float> a)
{
  int N = Length(a);
  qs(a, 0, N);
}

// ----------------------------------------------------------------------------
//
// check sorting of <a>
//
// ----------------------------------------------------------------------------
void check(Array<float> a)
{
  int N = Length(a);
  for (int i = 0; i < N-1; i++)
    {
      if (a[i] > a[i+1]) rt_abort("sorting error");
    }
}

// ----------------------------------------------------------------------------
//
// sorting main function
//
// ----------------------------------------------------------------------------
int qmain(int argc, char *argv[]) 
{
  int S = 1000;
  int N = 5;
  for (int i = 0; i < N; i++)
    {
      for (int k = 0; k < 5; k++)
        {
          Array<float> a(S);
          for (int j = 0; j < S; j++)
            {
              a[j] = rand();
            }
          qsort(a);
          check(a);
        }
      S *= 2;
    }
  return(0);
}

void init(RT_Argument *rt_arg, int argc, char *argv[]);

int main(int argc, char *argv[]) 
{
  RT_Argument rt_arg;
  init(&rt_arg, argc, argv);
  rt_arg.memory = 1000000;
  rt_arg.heap = 500000;
  rt_arg.blocks = 2;
  rt_arg.stack = 15000;
  exit(rt_main(qmain, 1, argv, rt_arg, 0));
}

// ----------------------------------------------------------------------------
// end of qsort.cc
// ----------------------------------------------------------------------------
// Local Variables: ***
// mode: C++ ***
// End: ***