4 n_squared_sort (float * value
, int * index
, int len
)
8 for (i
= 0; i
< len
-1; i
++)
10 for (j
= 0; j
< len
-1; j
++)
12 if (value
[j
] > value
[j
+1])
18 value
[j
] = value
[j
+1];
22 index
[j
] = index
[j
+1];
32 extern void* fake_malloc_radix(size_t size
);
35 radix_sort_tuples (int * value
, int * index
, int len
, int radix_bits
)
39 int numBuckets
= 1 << radix_bits
;
40 int bitMask
= numBuckets
- 1;
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
);
53 for (i
= 0; i
< len
; i
++) {
54 copy1_value
[i
] = value
[i
];
55 copy1_index
[i
] = index
[i
];
66 for (i
= 0; i
< len
; i
++)
68 copy1_value
[i
] += min
;
72 for (i
= 0; max
!= 0; max
= max
/ numBuckets
, i
++)
74 for (j
= 0; j
< numBuckets
+ 2; j
++)
81 for (j
= 0; j
< len
; j
++)
83 int myBucket
= (int) (((int) copy1_value
[j
]) >> denShift
) & bitMask
;
87 for (j
= 1; j
< numBuckets
; j
++)
89 buckets
[j
] += buckets
[j
-1];
94 for (j
= 0; j
< len
; j
++)
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
];
103 denShift
+= radix_bits
;
105 tmp_value
= copy1_value
;
106 copy1_value
= copy2_value
;
107 copy2_value
= tmp_value
;
109 tmp_index
= copy1_index
;
110 copy1_index
= copy2_index
;
111 copy2_index
= tmp_index
;
114 max
= copy1_value
[0];
115 for (i
= 0; i
< len
; i
++) {
116 if (max
< copy1_value
[i
]) {
117 max
= copy1_value
[i
];
121 for (i
= 0; i
< len
; i
++)
123 copy1_value
[i
] -= min
;
126 for (i
= 0; i
< len
; i
++)
128 value
[i
] = copy1_value
[i
];
129 index
[i
] = copy1_index
[i
];
136 insertion_sort (float * value
, int * index
, int len
)
140 for (i
= 1; i
< len
; i
++)
147 cur_index
= index
[i
];
150 while (empty
> 0 && current
< value
[empty
-1])
152 value
[empty
] = value
[empty
-1];
153 index
[empty
] = index
[empty
-1];
157 value
[empty
] = current
;
158 index
[empty
] = cur_index
;
166 partition (float * array
, int * index
, int low
, int high
)
168 int left
, right
, mid
;
173 mid
= (low
+ high
) / 2;
177 /* choose pivot as median of 3: low, high, and mid */
178 if ((array
[low
] - array
[mid
]) * (array
[high
] - array
[low
]) >= 0)
180 else if ((array
[mid
] - array
[low
]) * (array
[high
] - array
[mid
]) >= 0)
185 /* store value,index at the pivot */
189 /* swap pivot with the first entry in the list */
190 array
[pivot
] = array
[low
];
193 index
[pivot
] = array
[pivot
];
196 /* the quicksort itself */
199 while (array
[left
] <= cur
&& left
< high
)
201 while (array
[right
] > cur
)
208 tmp_val
= array
[right
];
209 array
[right
] = array
[left
];
210 array
[left
] = tmp_val
;
212 tmp_idx
= index
[right
];
213 index
[right
] = index
[left
];
214 index
[left
] = tmp_idx
;
218 /* pivot was in low, but now moves into position at right */
219 array
[low
] = array
[right
];
222 index
[low
] = index
[right
];
230 quicksort_inner (float * array
, int * index
, int low
, int high
)
233 int length
= high
- low
+ 1;
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
);
247 int quicksort (float * array
, int * index
, int len
)
249 quicksort_inner (array
, index
, 0, len
-1);
250 insertion_sort (array
, index
, len
);