benchmarks/sort/sort.c

   1 #include "sort.h"
   2
   3 int
   4 n_squared_sort (float * value, int * index, int len)
   5 {
   6   int i, j;
   7
   8   for (i = 0; i < len-1; i++)
   9   {
  10     for (j = 0; j < len-1; j++)
  11     {
  12       if (value[j] > value[j+1])
  13       {
  14         double val_tmp;
  15         int idx_tmp;
  16
  17         val_tmp = value[j];
  18         value[j] = value[j+1];
  19         value[j+1] = val_tmp;
  20
  21         idx_tmp = index[j];
  22         index[j] = index[j+1];
  23         index[j+1] = idx_tmp;
  24       }
  25     }
  26   }
  27
  28   return 0;
  29 }
  30
  31
  32 extern void* fake_malloc_radix(size_t size);
  33
  34 int
  35 radix_sort_tuples (int * value, int * index, int len, int radix_bits)
  36 {
  37   int i, j;
  38   int max, min;
  39   int numBuckets = 1 << radix_bits;
  40   int bitMask = numBuckets - 1;
  41   int denShift;
  42
  43   int * buckets = fake_malloc_radix ((numBuckets + 2) * sizeof(int));
  44   int * copy1_value = fake_malloc_radix (sizeof(int) * len);
  45   int * copy1_index = fake_malloc_radix (sizeof(int) * len);
  46   int * copy2_value = fake_malloc_radix (sizeof(int) * len);
  47   int * copy2_index = fake_malloc_radix (sizeof(int) * len);
  48   int * tmp_value;
  49   int * tmp_index;
  50
  51   max = value[0];
  52   min = value[0];
  53   for (i = 0; i < len; i++) {
  54     copy1_value[i] = value[i];
  55     copy1_index[i] = index[i];
  56     if (max < value[i]) {
  57       max = value[i];
  58     }
  59     if (min > value[i]) {
  60       min = value[i];
  61     }
  62   }
  63   min = -min;
  64   max += min;
  65
  66   for (i = 0; i < len; i++)
  67   {
  68     copy1_value[i] += min;
  69   }
  70
  71   denShift = 0;
  72   for (i = 0; max != 0; max = max / numBuckets, i++)
  73   {
  74     for (j = 0; j < numBuckets + 2; j++)
  75     {
  76       buckets[j] = 0;
  77     }
  78
  79     buckets += 2;
  80
  81     for (j = 0; j < len; j++)
  82     {
  83       int myBucket = (int) (((int) copy1_value[j]) >> denShift) & bitMask;
  84       buckets[myBucket]++;
  85     }
  86
  87     for (j = 1; j < numBuckets; j++)
  88     {
  89       buckets[j] += buckets[j-1];
  90     }
  91
  92     buckets--;
  93
  94     for (j = 0; j < len; j++)
  95     {
  96       int myBucket = (int) (((int) copy1_value[j]) >> denShift) & bitMask;
  97       int index = buckets[myBucket]++;
  98       copy2_value[index] = copy1_value[j];
  99       copy2_index[index] = copy1_index[j];
 100     }
 101
 102     buckets--;
 103     denShift += radix_bits;
 104
 105     tmp_value = copy1_value;
 106     copy1_value = copy2_value;
 107     copy2_value = tmp_value;
 108
 109     tmp_index = copy1_index;
 110     copy1_index = copy2_index;
 111     copy2_index = tmp_index;
 112   }
 113
 114   max = copy1_value[0];
 115   for (i = 0; i < len; i++) {
 116     if (max < copy1_value[i]) {
 117       max = copy1_value[i];
 118     }
 119   }
 120
 121   for (i = 0; i < len; i++)
 122   {
 123     copy1_value[i] -= min;
 124   }
 125
 126   for (i = 0; i < len; i++)
 127   {
 128     value[i] = copy1_value[i];
 129     index[i] = copy1_index[i];
 130   }
 131
 132   return 0;
 133 }
 134
 135 int
 136 insertion_sort (float * value, int * index, int len)
 137 {
 138   int i;
 139
 140   for (i = 1; i < len; i++)
 141   {
 142     double current;
 143     int cur_index;
 144     int empty;
 145
 146     current = value[i];
 147     cur_index = index[i];
 148     empty = i;
 149
 150     while (empty > 0 && current < value[empty-1])
 151     {
 152       value[empty] = value[empty-1];
 153       index[empty] = index[empty-1];
 154       empty--;
 155     }
 156
 157     value[empty] = current;
 158     index[empty] = cur_index;
 159   }
 160
 161   return 0;
 162 }
 163
 164
 165 int
 166 partition (float * array, int * index, int low, int high)
 167 {
 168   int left, right, mid;
 169   int pivot;
 170   float cur;
 171   int idx;
 172
 173   mid = (low + high) / 2;
 174   left = low;
 175   right = high;
 176
 177   /* choose pivot as median of 3: low, high, and mid */
 178   if ((array[low] - array[mid]) * (array[high] - array[low]) >= 0)
 179     pivot = low;
 180   else if ((array[mid] - array[low]) * (array[high] - array[mid]) >= 0)
 181     pivot = mid;
 182   else
 183     pivot = high;
 184
 185   /* store value,index at the pivot */
 186   cur = array[pivot];
 187   idx = index[pivot];
 188
 189   /* swap pivot with the first entry in the list */
 190   array[pivot] = array[low];
 191   array[low] = cur;
 192
 193   index[pivot] = array[pivot];
 194   index[low] = idx;
 195
 196   /* the quicksort itself */
 197   while (left < right)
 198   {
 199     while (array[left] <= cur && left < high)
 200       left++;
 201     while (array[right] > cur)
 202       right--;
 203     if (left < right)
 204     {
 205       float tmp_val;
 206       int tmp_idx;
 207
 208       tmp_val = array[right];
 209       array[right] = array[left];
 210       array[left] = tmp_val;
 211
 212       tmp_idx =  index[right];
 213       index[right] = index[left];
 214       index[left] = tmp_idx;
 215     }
 216   }
 217
 218   /* pivot was in low, but now moves into position at right */
 219   array[low] = array[right];
 220   array[right] = cur;
 221
 222   index[low] = index[right];
 223   index[right] = idx;
 224
 225   return right;
 226 }
 227
 228
 229 int
 230 quicksort_inner (float * array, int * index, int low, int high)
 231 {
 232   int pivot;
 233   int length = high - low + 1;
 234
 235   if (high > low)
 236   {
 237     if (length > MAX_THRESH) {
 238       pivot = partition (array, index, low, high);
 239       quicksort_inner (array, index, low, pivot-1);
 240       quicksort_inner (array, index, pivot+1, high);
 241     }
 242   }
 243
 244   return 0;
 245 }
 246
 247 int quicksort (float * array, int * index, int len)
 248 {
 249   quicksort_inner (array, index, 0, len-1);
 250   insertion_sort (array, index, len);
 251
 252   return 0;
 253 }