dol/examples/example1/src/quicksort.c

   1 #include <stdio.h>
   2 #include <math.h>
   3
   4 #include "quicksort.h"
   5
   6 int smaller_arr(int *dst, int *src, int pivot,int len)
   7 {
   8   int i;
   9   int num=0;
  10   for(i=0;i<len;i++)
  11   {
  12     if(src[i]<=pivot)
  13     {
  14       dst[num++]=src[i];
  15     }
  16   }
  17   return num;
  18 }
  19
  20 int bigger_arr(int *dst, int *src, int pivot,int len)
  21 {
  22   int i;
  23   int num=0;
  24   for(i=0;i<len;i++)
  25   {
  26     if(src[i]>pivot)
  27     {
  28       dst[num++]=src[i];
  29     }
  30   }
  31   return num;
  32 }
  33
  34 int median_const(int len, int * array)
  35 {
  36   int i,j;
  37   int desired_rank = ceil(len/2);
  38
  39   for(i=0;i<len;i++)
  40   {
  41     int rank = 1;
  42     for(j=0;j<len;j++)
  43     {
  44       /* FIXME: exception handling */
  45       if(i!=j && array[j]>array[i])
  46         rank++;
  47     }
  48
  49     if(rank==desired_rank)
  50       return array[i];
  51   }
  52   return array[0];
  53 }
  54
  55 int select_med(int size, int * array)
  56 {
  57   int ret;
  58   int * array_of_median;
  59   int len = ceil(size/5);
  60   int i,j;
  61
  62   /* divide array into groups of five elements */
  63   array_of_median = malloc(sizeof(int)*len);
  64
  65   for(i=0;i<len;i++)
  66   {
  67     if(i!=len-1)
  68       array_of_median[i] = median_const(5,array+5*i);
  69     else
  70       array_of_median[i] = median_const(len%5,array+5*i);
  71   }
  72
  73   /* call itself recursively */
  74   ret = select_med(len, array_of_median);
  75
  76   /* release */
  77   free(array_of_median);
  78
  79   return ret;
  80 }
  81
  82
  83
  84 void quicksort_init(DOLProcess *p) {
  85     p->local->index = 0;
  86 }
  87
  88 int quicksort_fire(DOLProcess *p) {
  89
  90   int len=LENGTH;
  91   int * array;
  92   int median;
  93   int down,up;
  94
  95   /* receive the 'size' / 'array' */
  96   DOL_read((void*)PORT_IN1, &len, sizeof(int), p);
  97   DOL_read((void*)PORT_IN2, array, sizeof(int)*len, p);
  98
  99   /* selection */
 100   median = select_med(len, array);
 101
 102   /* divide */
 103   down = 0; up =0;
 104   down=smaller_arr(arr1,array,median,len);
 105   up=bigger_arr(arr2,array,median,len);
 106
 107   // down + up == len
 108
 109   /* sort */
 110   quick
 111
 112   /* merge */
 113
 114   /* send the 'size' / 'sorted array' */
 115   DOL_write((void*)PORT_OUT1, &len, sizeof(int), p);
 116
 117   DOL_detach(p);
 118   return -1;
 119 }
 120