| 1 |
#include "ind_sort.h" |
| 2 |
|
| 3 |
void exchange(int *ind_list, double *vals, int i, int j) |
| 4 |
{ |
| 5 |
int temp_int; |
| 6 |
double temp_dbl; |
| 7 |
|
| 8 |
temp_int = ind_list[i]; |
| 9 |
ind_list[i] = ind_list[j]; |
| 10 |
ind_list[j] = temp_int; |
| 11 |
|
| 12 |
temp_dbl = vals[i]; |
| 13 |
vals[i] = vals[j]; |
| 14 |
vals[j] = temp_dbl; |
| 15 |
} |
| 16 |
|
| 17 |
/*===========================================================================*/ |
| 18 |
|
| 19 |
int partition(int *ind_list, double *vals, int len) |
| 20 |
{ |
| 21 |
|
| 22 |
int i=0, j, pivot; |
| 23 |
double middle; |
| 24 |
|
| 25 |
j=len-1; |
| 26 |
/*pivot=random() % len;*/ |
| 27 |
pivot=0; |
| 28 |
middle = vals[pivot]; |
| 29 |
|
| 30 |
exchange(ind_list, vals, pivot, j); |
| 31 |
|
| 32 |
while (i<j){ |
| 33 |
while ((i<j) && (vals[i] >= middle)) |
| 34 |
i++; |
| 35 |
while ((i<j) && (vals[j] <= middle)) |
| 36 |
j--; |
| 37 |
if (i<j) |
| 38 |
exchange(ind_list, vals, i, j); |
| 39 |
} |
| 40 |
if (i!=len-1) |
| 41 |
exchange(ind_list, vals, i, len-1); |
| 42 |
|
| 43 |
return(i); |
| 44 |
} |
| 45 |
|
| 46 |
/*===========================================================================*/ |
| 47 |
|
| 48 |
void ind_sort(int *ind_list, double *vals, int len) |
| 49 |
{ |
| 50 |
|
| 51 |
int pivot; |
| 52 |
|
| 53 |
pivot=partition(ind_list, vals, len); |
| 54 |
|
| 55 |
if (pivot>=2) |
| 56 |
ind_sort(ind_list, vals, pivot); |
| 57 |
if (pivot <= len - 3) |
| 58 |
ind_sort(ind_list+pivot+1, vals+pivot+1, len-pivot-1); |
| 59 |
} |
| 60 |
|