X-Git-Url: http://sraa.de/git/?a=blobdiff_plain;f=dol%2Fexamples%2Fexample1%2Fsrc%2Fquicksort.c;fp=dol%2Fexamples%2Fexample1%2Fsrc%2Fquicksort.c;h=5512fda92556e14ebcb2bf52bd8fb1e6f2d2f65a;hb=8c411cf24ed0eb889191aaeafd8fa1e69081df42;hp=0000000000000000000000000000000000000000;hpb=dea7a4fb1ed110d3ce6e6d9255103d724bd66c0e;p=jump.git

diff --git a/dol/examples/example1/src/quicksort.c b/dol/examples/example1/src/quicksort.c
new file mode 100644
index 0000000..5512fda
--- /dev/null
+++ b/dol/examples/example1/src/quicksort.c
@@ -0,0 +1,120 @@
+#include <stdio.h>
+#include <math.h>
+
+#include "quicksort.h"
+
+int smaller_arr(int *dst, int *src, int pivot,int len)
+{
+  int i;
+  int num=0;
+  for(i=0;i<len;i++)
+  {
+    if(src[i]<=pivot)
+    {
+      dst[num++]=src[i];
+    }
+  }
+  return num;
+}
+
+int bigger_arr(int *dst, int *src, int pivot,int len)
+{
+  int i;
+  int num=0;
+  for(i=0;i<len;i++)
+  {
+    if(src[i]>pivot)
+    {
+      dst[num++]=src[i];
+    }
+  }
+  return num;
+}
+
+int median_const(int len, int * array)
+{
+  int i,j;
+  int desired_rank = ceil(len/2);
+
+  for(i=0;i<len;i++)
+  {
+    int rank = 1;
+    for(j=0;j<len;j++)
+    {
+      /* FIXME: exception handling */
+      if(i!=j && array[j]>array[i])
+        rank++;
+    }
+
+    if(rank==desired_rank)
+      return array[i];
+  }
+  return array[0];
+}
+
+int select_med(int size, int * array)
+{
+  int ret;
+  int * array_of_median;
+  int len = ceil(size/5);
+  int i,j;
+
+  /* divide array into groups of five elements */
+  array_of_median = malloc(sizeof(int)*len);
+
+  for(i=0;i<len;i++)
+  {
+    if(i!=len-1)
+      array_of_median[i] = median_const(5,array+5*i);
+    else
+      array_of_median[i] = median_const(len%5,array+5*i);
+  }
+
+  /* call itself recursively */
+  ret = select_med(len, array_of_median);
+
+  /* release */
+  free(array_of_median);
+
+  return ret;
+}
+
+
+
+void quicksort_init(DOLProcess *p) {
+    p->local->index = 0;
+}
+
+int quicksort_fire(DOLProcess *p) {
+
+  int len=LENGTH;
+  int * array;
+  int median;
+  int down,up;
+
+  /* receive the 'size' / 'array' */
+  DOL_read((void*)PORT_IN1, &len, sizeof(int), p); 
+  DOL_read((void*)PORT_IN2, array, sizeof(int)*len, p); 
+
+  /* selection */
+  median = select_med(len, array);
+
+  /* divide */
+  down = 0; up =0;
+  down=smaller_arr(arr1,array,median,len);
+  up=bigger_arr(arr2,array,median,len);
+
+  // down + up == len
+
+  /* sort */
+  quick
+  
+  /* merge */
+
+  /* send the 'size' / 'sorted array' */
+  DOL_write((void*)PORT_OUT1, &len, sizeof(int), p); 
+
+  DOL_detach(p);
+  return -1;
+}
+