/*----------------------------------------------------------------------*/ /* LINEAR PROBING SORT */ /* Adapted by J. Teuhola from G. H. Gonnet & */ /* R. Baeza-Yates: Handbook of Algorithms and Data Structures, */ /* 2nd Edition, Addison-Wesley Publishing Company, 1991. */ /*----------------------------------------------------------------------*/ #define element float #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 1.4n. */ /* The minimum key value should be larger than Lowvalue+1. */ /*----------------------------------------------------------------------*/ void linear_probing_sort(r, w, n, upper) element r[], w[]; int n, upper; { int i, j, m; float x, aux, factor, low; pair p; m = 1.4 * n; /* The magic enlargement ratio */ p = minmax(r, n); low = p.min-1.0; if (p.max > p.min) { factor = (float) m / (p.max-p.min); for (j=0; j low; i++) /* Probe */ { if (x upper) goto error; } w[i] = x; } i = 0; for (j=0; j low) r[i++] = w[j]; return; error: printf("*** Out of space ***\n"); } } /* End of linear_probing_sort */