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


External Quicksort


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 ); };

C source (446.sort.c)



© Addison-Wesley Publishing Co. Inc.