Problem Solving: In-place Array Segregation

Learn to solve different in-place array segregation problems.

We'll cover the following

In this lesson, we’ll revisit problems involving segregating (separating or dividing) the array without using extra memory.

In-place segregation

In the previous lesson, we segregated the values by creating extra arrays, copying the same types of values in them, and replacing the values in a certain order in the main array.

But what if we had to segregate the values without using the extra space? We would need to come up with a way to shift the values in the D array without creating new arrays.

Take the even and odd value segregation as an example.

Approach 1: The shifting approach

Let’s take a scenario where we would like to move all even numbers to the left of the array and odd numbers to the right of the array.

The idea is the following:

  • First, we keep iterating to the right as far as we are having even numbers (as they are already in the correct (left position). We find the first index that is not even and save it in ei.

  • Now, we start a loop with another variable oi, which keeps moving forward, starting from ei (could be ei+1), until it finds an even number.

    • If an even value is found, we shift that even number back toward the left until that even number reaches the right evens region (that is the location of ei). Now, we increment ei and keep moving forward oi until all the elements are checked.

Look at the animation below:

Press + to interact
void segregateEvensOdds_SlowInPlace(int D[], int size)
{
    int ei = 0, oi = 0;
    while(D[ei]%2==0)
        ei++;
        
    for(int oi=ei; oi<size; oi++)
    {
        if(D[oi]%2==0)  // even found hence all the odds shifted to the right hence we have to swap till the last index of even
        {
            for(int t=oi; t-1>=ei; t--)
            {
                swap(D[t], D[t-1]);
            }
        }
    }
}

The complete code is given below. Click “Run” to see its output:

8
4 22 14 1 5 3 4 8
Inplace segregation with segregateEvensOdds_Slow() function

Approach 2: Segregating without shifting with two pointers

Instead of shifting all the odd values to the right, we can just swap the first odd values with the upcoming even value and increment the ei pointer. It does not make sense that we do the entire shifting—replacing the first odd with the new even number should suffice.

This way, the order of even and odd values may be changed, but that is fine because we are only interested in efficiency rather than the order in which evens and odds are placed (we just want segregation no matter what order of evens and odds it is).

Look at the animation below:

We've implemented this approach inside the segregateEvensOdds_without_shiftingInPlace() function below:

// another way to implement the above program 
void segregateEvensOdds_without_shiftingInPlace(int D[ ], int size)
{
    int ei = 0, oi = 0;
    while(D[ei]%2==0)
        ei++;
    oi = ei;
    while(oi<size)
    {
        while(oi<size && D[oi]%2==1)  // while you find an odd number keep moving
            oi++;
        if(oi<size)
        {
            swap(D[ei], D[oi]);
            ei++;
        }
    }
}
Alternative implementation of segregateEvensOdds_without_shiftingInPlace() function

Instruction: Update the above playground and test it using this function.

Approach 3: Extreme shrinking approach

We follow the steps below in this approach:

  1. We have two variables (si = 0 and ei = size - 1), we call them extremes.

  2. For si, keep increasing the values as long as, they are even (the loop of si will break on the first odd number in the left region) and the value of ei keeps decreasing as long as the values are odd (the loop of ei will break on the first even number in the right region).

  3. Now, if the si is lesser than the ei, we swap their values, and start proceeding (step 2 again). This process should be repeated until si<ei.

This approach is efficient because it will read all the values exactly once. Also, this idea can easily be extended to any segregating problem.

Look at the animation below to understand how theextreme shrinking approach works.

Look at the code below. Execute the code step by step for better understanding:

8
4 22 14 1 5 3 4 8
Inplace segregation with segregateEvensOdds_ExtremeShrinking() function

Practice Exercise

Instruction: Solve the following two tasks in the above playground.

Task 1: Take the above first two (0’s and 1s segregation, primes and composites segregation) problems in the previous lesson “Practice exercise” and solve one with “Approach 2: Without shifting” and the other with “Approach 3: Extreme shrinking”.

See the solution for “Approach 2: Without shifting” below:

See the solution for “Approach 3: Extreme shrinking” below:

Task 2: Take “Problem Solving: Array Segregation””, and solve it with “Approach 3: Extreme shrinking” in the following fashion:

  1. First, perform segregation by considering mangoes and apples as one fruit and bananas as another.
  2. Once bananas are to the left, perform segregation again only in the mangoes and apples part by segregating mangoes and apples.