/*----------------------------------------------------------------------*/ /* ADAPTIVE IN-PLACE LINEAR PROBING SORT */ /* Copyright (C) 1996 S. Carlsson */ /* J. Katajainen */ /* J. Teuhola */ /* Published in DIKU Report 96/31, Department of Computer Science, */ /* University of Copenhagen, Denmark. */ /* */ /* This program is free software; you can redistribute it and/or modify */ /* it under the terms of the GNU General Public License; version 2 of */ /* the License or any later version. There is no warranty for the */ /* program. See the GNU General Public License for more details. */ /*----------------------------------------------------------------------*/ #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. */ /*----------------------------------------------------------------------*/ 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 pivot get left to the rest. */ /* The right-to-left wheel-technique is used, because there should be */ /* fewer elements <= pivot. The hole technique is applied to minimize */ /* the moves. The border is returned. */ /*----------------------------------------------------------------------*/ int right_to_left_partition(pivot, r, low, n) element pivot, r[]; int low, n; { int i, j; element x; i = n-1; /* Start with empty wheel */ x = r[i]; /* Dig the hole */ for (j=i-1; j>=low; j--) if (r[j]<=pivot) /* Turn wheel? */ { r[i--] = r[j]; r[j] = r[i]; } r[i] = x; /* Fill the hole */ if (x<=pivot) return i; else return (i+1); } /* End of left_to_right_partition */ #endif #ifndef DISTRIBUTE #define DISTRIBUTE /*----------------------------------------------------------------------*/ /* Distribute elements r[mid..n-1] to r[low..mid-1] by linear probing. */ /* Locations r[mid..] may have to be used as overflow area. */ /*----------------------------------------------------------------------*/ void distribute(min, pivot, r, low, mid, n) element min, pivot, r[]; int low, mid, n; { int i, addr; float factor; element x, y; /* Calculate the interpolation coefficient: */ factor = (float)(mid-low)/(pivot-min); for (i=mid; i