+#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;
+}
+