Suppose the entering freshmen class at some university has N students. The in-

formation pertinent to each student in the class (name, sex, identication number,

etc.) can be found in some element of A, an array of records indexed from 1 to

N. Assume the records are in some random order, and that we wish to rearrange

the array so that all the female records precede all the male records. Give a linear

(O(N)) time algorithm which performs this \partial sort" on A. Assume \sex" is a

eld in each record, with value \Male" or \Female".