/*----------------------------------------------------------------------*/ /* BUCKET SORT WITH COUNT ARRAY */ /* Adapted by J. Teuhola from [G. H. Gonnet & */ /* R. Baeza-Yates: Handbook of Algorithms and Data Structures, */ /* 2nd Edition, Addison-Wesley Publishing Company, 1991], where the */ /* method is called INTERPOLATION SORT. */ /*----------------------------------------------------------------------*/ #ifndef element #define element float #endif #ifndef PAIR #define PAIR typedef struct { element min, max; } pair; #endif #ifndef MINMAX #define MINMAX /*----------------------------------------------------------------------*/ /* Determine the minimum & maximum of r[0..n-1]. A special technique */ /* with 1.5 comparisons per element is applied. The result is returned */ /* as the minimum & maximum -pair. */ /*----------------------------------------------------------------------*/ static pair minmax(r, n) element r[]; int n; { int i; element x, y, min, max; pair p; min = r[n-1]; max = min; /* Initial */ for (i=0; imax) max = y; } else { if (x>max) max = x; if (y aux; j--) r[j+1] = r[j]; r[j+1] = aux; } } /*----------------------------------------------------------------------*/ /* The actual sort routine just collects the phases. */ /* The array parameters r, aux and addr should all have space */ /* allocation of 0..n-1, whereas the array 'count' needs only 0..n/10. */ /*----------------------------------------------------------------------*/ void bucketsort(r, aux, addr, count, n) element r[], aux[]; int addr[], count[], n; { pair p; int nbuckets; p = minmax(r, n); if (p.min < p.max) { nbuckets = n/10; if (nbuckets == 0) nbuckets = 1; b_sort(r, aux, addr, count, n, nbuckets, p.min, p.max); i_sort_after_b_sort(r, n, p.min); } } /* End of bucketsort */