### Order the sequence in an array array sorting general    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (3716)

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: 7 years ago 0 0 Edit 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]; EndTime 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 .