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


Interpolation sort (Pascal version available)


sort( r, lo, up ) ArrayToSort r; int lo, up; {ArrayIndices iwk; ArrayToSort out; ArrayEntry tempr; int i, j; for (i=lo+1; i<=up; i++) iwk[i] = 0; 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--) out[ iwk[ phi(r[i].k,lo,up) ]-- ] = r[i]; for (i=lo; i<=up; i++) r[i] = out[i]; 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 (416.sort.c) Pascal source (416.sort.p)



© Addison-Wesley Publishing Co. Inc.