Order the sequence in an array
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2673)

Suppose you are given an array A of N students in a class indexed from 1 to N . Each student has name , gender and identification number . Assuming that the records are in random order can you design an algorithm that rearrange the array so that all the female records precede all the male records?


Posted Answers

Let us assume that there is atleast one male and one female in array A .


Initialize malePointer =1, femalePointer = N;
while(malePointer < femalePointer)
Begin
while malePointer points to a female's record in A
malePointer++;
while femalePointer points to a male's record in A
femalePointer--;
if(malePointer < femalePointer)
swap A[malePointer] with A[femalePointer];
End


Time complexity of this algorithm is \( O(N) \). malePointer moves from smaller to larger indices and femalePointer from larger to smaller. Since the algorithm terminates when these two pointers have crossed there will be N pointer changes and at each pointer change there is a constant number of additional steps. Therefore, the time complexity of the algorithm is constant times pointer changes, i.e , N .

You need to Sign In to post your solution.