[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.