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

ID: 3699230 • Letter: S

Question

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

Algorithm:

Step1: Initialize two iterator indices i = 1 and j = N .

Step2: Run while loop untill i < j and execute below statements

Step3: find index of record from left side where sex = "Male"

while(arr[i].sex != "Male" )

i++;

Step4: find index of record from right side where sex = "Female"

while(arr[j].sex != "Female" )

j--;

Step4: Swap ( arr[i], arr[j]) because we are only concerned to push all records of females befores males, we do not need to do anything extra.

Step5: Increment i by 1 i.e; i++ and decrement j by 1 i.e; j-- for next iteration.

Step6: Run Step2 to Step5 untill i<j

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.