#include #define STYPE double void bsort(arr, nr) STYPE *arr; int nr; { int last, first; int d = nr / 2 + 1; /* Quick bubble sort: */ while (d > 1) { int nr_swapped = 0, i; STYPE *arr1 = arr, *arr2 = arr + d; last = nr - d; for (i = 0; i < last; i++, arr1++, arr2++) if (*arr1 > *arr2) { STYPE h = *arr1; *arr1 = *arr2; *arr2 = h; nr_swapped++; } if (nr_swapped == 0) d = d / 3; else { double nd = (double)nr_swapped/(double)last; nd = (1 + sqrt(nd))/2; d = (int)( d * nd ); } if (d < 1) d = 1; } /* Normale left/right bubble-sort algorithme: */ first = 0; last = nr - 1; while (first < last) { int n_first, n_last, i; STYPE *arr1 = arr + first, *arr2 = arr1 + 1; n_last = first; for (i = first; i < last; i++, arr1 = arr2, arr2++) if (*arr1 > *arr2) { STYPE h = *arr1; *arr1 = *arr2; *arr2 = h; n_last = i; } last = n_last; if (first < last) { arr2 = arr + last; arr1 = arr2 - 1; n_first = last; for (i = last; i > first; i--, arr2 = arr1, arr1--) if (*arr1 > *arr2) { STYPE h = *arr1; *arr1 = *arr2; *arr2 = h; n_first = i; } first = n_first; } } }