Question

1. Each baby has brown hair or purple hair. Design a one-pass and in- place and linear time algorithm to sort the babies according to their hair color: brown hair babies followed by purple hair babies. In your algorithm, you must use only two pointers. (a). Please tell me explicitly what the constraints are we put on those two pointers (i.e., you interpret intuitively, and possibly with some drawings on the meanings of "one-pass", "in-place", and "linear-time".). (b). The thought process of designing an algorithm is really important - you have to walk in the right direction at the first trial. When you design the algorithm, you have to bear in mind simontaneously the three constraints ("one-pass", "in-place", and "linear-time") while moving the two pointers in your mind on the array of babies. Please write down the thought process of your design of the algorithm and in particular, mentioning among the three constraints, which one you consider the first and why. (c). Please write on almost working psuedo-code with comment.

Answer 1

As it is given in the problem that the color of the babies' hair is either brown or purple, so let's use 0 for denoting brown-haired babies and 1 for violet-haired babies. So our array which we are supposed to sort now contains only 0 and 1.

Lets first see what the three constraints actually mean..

1. One-pass: It means that we should process(do manipulation or visit) each element a single time only. What this essentially means is that we should come up with an algorithm which will go through all the elements at most 1 time. Once it has visited an element it shouldn't visit the same element again.

2. In-place: It means that all the operations or manipulations that we are doing upon the elements should be done in the given array itself. No extra or temporary space should be used for processing any element. (Exception: Sometimes when we're dealing with huge amounts of data, in-place means that we're not taking too much extra space, some small constant like 2 or 5 extra variables (temporary) can be used. This comes under the space complexity of programs and I think this is a bit above the current required level of the answer, I can expand on this if you want).

3. Linear-time: Linear time means that the time complexity of the algorithm should be linear, which essentially means that for an input of 'n' elements it should take O(n) time. O(n) is called as the Big-O asymptotic notation, which tells that in the worst case possible our algorithm will take order of 'n' time(which can be like 1.5n or 2n or 3n, as long as the constant is not comparable to n).

NOTE: Linear-time and one-pass initially look similar but one-pass allows only one-time processing of data while linear-time can allow any constant amount of time(with that constant being relatively very small as compared to n)

First I would consider linear-time then one-pass because the earlier is easier to get than the latter, and at last we can think about in-place, this should also be the general way in one should think while tackling such questions.

As mentioned, we have to use only two pointers so will take two pointers, lets call them left and right.

We will initialise left with 0(starting index of the array, index of the first element) and right with the last index or the index of the last element which would be n - 1, considering n babies or A.size() - 1(size of array - 1 which is the last index).

Now we will compare the elements at these two positions, i.e. on left and right. Now two cases can arise:

1. The element at A[left] is 1, so we need to put it after all the 0s, so we will simply swap the values of elements present at left and right. Now we can be sure that the element at right is a 1 so we will decrease the value of right pointer by 1, since the element at right is already in its sorted position which is at last. We are still not sure if the element at left is a 0 or a 1, so we won't change the value of A[left].

2. The element at A[left] is 0, here we can simply see that this is sorted, as all 0s should be followed by all 1s and we are getting a 0 at the left-most unprocessed element. Here we increase the value of left by 1.

NOTE: Here we are trying to process the array in such a manner that the elements before the left pointer are all 0s and after the right pointer are all 1s.

We keep doing this until our left pointers become bigger than our right pointer. If this happens then we will break out of the while loop and we can safely say that all the elements in the array have been sorted accordingly.

At maximum either one pointer can go all the from 0 to n-1(in case of left pointer) or from n-1 to 0(in case of right pointer) or they meet somewhere in the middle. Either way, we can say that at each step one element is getting processed(since either left or right pointer values are changed), so it is a linear-time & one-pass algorithm. Also, we are not using any other variable except the left and right pointer so it's in-place too.

WORKING CODE:

void sortArrayByParity(int A[], int n) //Function to sort our array.
{
int left = 0, right = n - 1;
while (left < right) //This loops runs n times
{
if (A[left] == 1)
{   
swap (A[l], A[r]);
--right;
}
else
{
++left;
}
}
for (int i = 0; i < n; ++i) //For printing the sorted array.
cout << A[i] << " ";
}