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?
Let us assume that there is atleast one male and one female in array A .
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 .