CODEWITHSUNDEEP
c++algorithm
P.K.
P.K.

Reputation: 409

Intuition behind incrementing the iteration variable?

I am solving a question on LeetCode.com:

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, they use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. [The trivial counting sort cannot be used].

For the input: [2,0,2,1,1,0]; the output expected is: [0,0,1,1,2,2].

One of the highly upvoted solutions goes like this:

   public void sortColors(vector<int>& A) {
       if(A.empty() || A.size()<2) return;
       int low = 0; 
       int high = A.size()-1;
       for(int i = low; i<=high;) {
           if(A[i]==0) {
              // swap A[i] and A[low] and i,low both ++
              int temp = A[i];
              A[i] = A[low];
              A[low]=temp;
              i++;low++;
           }else if(A[i]==2) {
               //swap A[i] and A[high] and high--;
              int temp = A[i];
              A[i] = A[high];
              A[high]=temp;
              high--;
           }else {
               i++;
           }
       }
   }

My question is, why is i incremented when A[i]==0 and A[i]==1 and not when A[i]==2? Using pen and paper, the algorithm just works to give me the answer; but could you please provide some intuition?

Thanks!

Upvotes: 3

Views: 98

Answers (2)

n00ne
n00ne

Reputation: 259

That is, because for 0s and 1s, only items left of the current item are handled and those have already been reviewed / sorted. Only for 2s items from the right end of the array are handled, which haven't been looked at yet.

To be more specific: In this specific example only three different states are handled:

  1. the current item being reviewed equals 0: in this case this sorting algorithm just puts this item at the end of all zeros, which have already been sorted (aka A[low]). Also the item which was at A[low] before can only be a 0 or 1 (since they have already sorted) which means you can just swap with the current item and not break the sequence. Now the interesting part: up until now, every item from A[0] over A[low] to A[i] has been already sorted, so the next item which has to be reviewed will be A[i + 1], hence the i++
  2. the current item equals 1: in this case, no swapping has to be done, since all 0s and 1s has already been put in A[0] to A[i - 1] and all 2s have already been put at the end of the array. That means, the next item to be reviewed is A[i + 1], hence the i++
  3. the current item equals 2: in this case, the current item will be put at the end of the array, next to (i.e., to the left of) all the other already sorted 2s (A[high]). The item, which will be swapped from A[high] to A[i] has not been sorted yet and therefor has to be reviewed in the next step, hence th i = i;

Upvotes: 2

k_ssb
k_ssb

Reputation: 6272

This steps through the array and maintains the constraint that the elements 0..i are sorted, and all either 0 or 1. (The 2's that were there get swapped to the end of the array.)

When A[i]==0, you're swapping the element at i (which we just said was 0) with the element at low, which is the first 1-element (if any) in the range 0..i. Hence, after the swap, A[i]==1 which is OK (the constraint is still valid). We can safely move forward in the array now. The same is true if A[i]==1 originally, in which case no swap is performed.

When A[i]==2, you're essentially moving element i (which we just said was 2) to the end of the array. But you're also moving something from the end of the array into element i's place, and we don't know what that element is (because we haven't processed it before, unlike the A[i]==0 case). Hence, we cannot safely move i forward, because the new element at A[i] might not be in the right place yet. We need another iteration to process the new A[i].

Upvotes: 5

Related Questions