benchmarks/sort/sort.c

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