[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Interpolation (in-place) sort


sort( r, lo, up ) ArrayToSort r; int lo, up; {ArrayIndices iwk; ArrayEntry tempr; int i, j; for (i=lo; i<=up; i++) {iwk[i] = 0; r[i].k = -r[i].k;} iwk[lo] = lo-1; for (i=lo; i<=up; i++) iwk[ phi(-r[i].k,lo,up) ]++; for (i=lo; i<up; i++) iwk[i+1] += iwk[i]; for (i=up; i>=lo; i--) if ( r[i].k<0 ) do { r[i].k = -r[i].k; j = iwk[ phi( r[i].k, lo, up ) ]--; tempr = r[i]; r[i] = r[j]; r[j] = tempr; } while ( i != j ); for ( i=up-1; i>=lo; i-- ) { tempr = r[i]; for ( j=i+1; j<=up && (tempr.k>r[j].k); j++ ) r[j-1] = r[j]; r[j-1] = tempr; } };

C source (416b.sort.c)



© Addison-Wesley Publishing Co. Inc.