|
<![CDATA[
sort( a, b )
int a, b;
{int i, j, rlow, rupp, wlow, wupp, InBuff;
typekey MaxLower, MinUpper;
struct rec LastRead;
extern struct rec Buff[];
while ( b>a ) {
rupp = wupp = b;
rlow = wlow = a;
InBuff = 0;
MaxLower = MinimumKey;
MinUpper = MaximumKey;
i = a-1;
j = b+1;
/*** Partition the file ***/
while ( rupp >= rlow ) {
if ( rlow-wlow < wupp-rupp )
LastRead = ReadDirect( rlow++ );
else LastRead = ReadDirect( rupp-- );
if ( InBuff < M ) {
Buff[ InBuff++ ] = LastRead;
intsort( Buff, 0, InBuff-1 );
}
else {
if ( LastRead.k > Buff[M-1].k ) {
if ( LastRead.k > MinUpper ) j = wupp;
else MinUpper = LastRead.k;
WriteDirect( wupp--, LastRead);
}
else if ( LastRead.k < Buff[0].k ) {
if ( LastRead.k < MaxLower ) i = wlow;
else MaxLower = LastRead.k;
WriteDirect( wlow++, LastRead);
}
else if ( wlow-a < b-wupp ) {
WriteDirect( wlow++, Buff[0] );
MaxLower = Buff[0].k;
Buff[0] = LastRead;
intsort( Buff, 0, M-1 );
}
else { WriteDirect( wupp--, Buff[M-1] ) ;
MinUpper = Buff[M-1].k;
Buff[M-1] = LastRead;
intsort( Buff, 0, M-1 );
}
}
}
while ( InBuff>0 ) WriteDirect( wupp--, Buff[--InBuff] );
/*** sort the shortest subfile first ***/
if (i-a < b-j) { sort(a,i); a = j; }
else { sort(j,b); b = i; }
}
return( 1 );
};
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (446.sort.c) 