Search⌘ K
Home
Courses
Beginner to Advanced Computing and Logic Building

Problem Solving: Array Segregation

Learn to solve different array segregation problems.

We'll cover the following...

In this lesson, we’ll practice problems that involve segregating (separating or dividing) the array based on different conditions.

Segregation using extra memory

For instance, given an array, D, we want to segregate the array based on the even and odd values of the array.

Segregating evens and odds

For this, we might want to find the even values from D and store these even values in a separate array, (Es). We can do the same for the odd values and store the odd values in a separate array, (Os). We can make a function that separates the values into even and odd values, (segregateEvensOdds()).

After we’ve separated both the even and odd values, we can replace the values of D with the even and odd values. We can make a separate function to replace the values of the array (replaceEsFollowedByOs()).

Look at the animation below to understand what is happening inside the segregateEvensOdds() function.

Look at the implementation of the segregateEvensOdds() function in the widget below:

C++
void segregateEvensOdds(int D[], int size, int Es[], int &ECount, int Os[], int &OCount)
{   
    /* variables that will maintain the count of the 
       number of even and odd values and initializing them with 0 */
    ECount = OCount = 0;
    
    int ei = 0, oi = 0;
    for(int i=0; i<size ;i++)   /* could have been 
                                for(int i=0, ei=0, oi=0; i<size; i++) */
    {   
        // if the value is even
        if(D[i]%2 == 0)
        {
            // copy the even value to array Es
            Es[ei]=D[i];
            ei++, ECount++;
        }
        else // if the value is odd
        {
           // copy the odd value to array Os
            Os[oi] = D[i];
            oi++, OCount++;
        }
    }
}

We can make a function to display the array’s values (specialDisplay()).

C++
void specialDisplay(const char msg[], int A[], int size)
{
    cout << left << setw(25) << msg<< " = { ";
    for(int ai=0; ai<size; ai++)
    {
        cout << right <<setw(5)<<A[ai] << " ";
    }
    cout << "  }"<<endl;
}

Lastly, we add our function to replace the values:

C++
void replaceEsFollowedByOs(int D[ ], int Es[], int ECount, int Os[], int OCount)
{
    int di=0;   // indexing through D array
    // first writing Evens
    for(int ei=0; ei<ECount;    
                      ei++, di++) //incrementing both Es and Ds array indices
    {
        D[di] = Es[ei];
    }
    // first writing Odds
    for(int oi=0; oi<OCount; 
                           oi++, di++) //incrementing both Os and Ds array indices
    {
        D[di] = Os[oi];
    }
}

Look at the animation below to understand what is happening inside the replaceEsFollowedByOs() function.

The complete program is given below:

8
1 589 512 -4 -6 1 4 56
Complete implementation

Let’s practice a few of the interesting array segregating problems. If you need debugging at any instant, use the above playground for that.

Practice exercises

Exercise 1: Segregating 0’s and 1’s

Given an array of 0s and 1s, move all the 0s to the left and the 1s to the right.

Sample input:

1 0 0 1 0 1 0 0 0

Sample output:

Segregated 0s Array: 0 0 0 0 0 0 
Segregated 1s Array: 1 1 1
Segregated Array: 0 0 0 0 0 0 1 1 1

Write your solution here:

C++
void init(const char name[ ], int D[ ], int &size);
void specialDisplay(const char msg[ ], int A[ ], int size);
// Assume, you have these implementations available
void segregateZeroesOnes(int D[ ], int size, int Zs[ ], int &ZCount, int Os[ ], int &OCount)
{
    ZCount = OCount = 0;
    
    int zi = 0, oi = 0;
    for(int i=0; i<size ;i++)   
    {
        // add code here
    }
}
void replaceZsFollowedByOs(int D[ ], int Zs[ ], int ZCount, int Os[ ], int OCount)
{
    // add code here
}
int main()
{
    const int capacity = 100;
    int D[capacity]={}, size;
    int Zs[capacity]={}, ZCount,
        Os[capacity]={}, OCount;
    init("D.txt", D, size);
    specialDisplay("Read from file Data Ds: ", D, size);
    segregateZeroesOnes(D, size, Zs, ZCount, Os, OCount);
    specialDisplay("Zeros Array Zs: ", Zs, ZCount);
    specialDisplay("Ones Array Os: ", Os, OCount);
    replaceZsFollowedByOs(D, Zs, ZCount, Os, OCount);
    specialDisplay("Replaced Array - New Ds: ", D, size);
    return 0;
}

Exercise 2: segregating composites and primes

Given an array of prime and composite numbers, move all primes to the left and the non-primes to the right.

Sample input:

10 5 7 9 6 8

Sample output:

Prime Array:      5 7  
Composite Array:  10 9 6 8
Segregated Array: 5 7 10 9 6 8

Write your code here:

C++
void init(const char name[ ], int D[ ], int &size);
void specialDisplay(const char msg[ ], int A[ ], int size);
// Assume, you have these implementations available
void segregatePrimesComposites(int D[ ], int size, int Ps[ ], int &PCount, int Cs[ ], int &CCount)
{
    PCount = CCount = 0;
    
    int pi = 0, zi = 0;
    for(int i=0; i<size ;i++)   
    {
        // add code here
    }
}
void replacePsFollowedByCs(int D[ ], int Ps[ ], int PCount, int Cs[ ], int CCount)
{
    // add code here
}
int main()
{
    const int capacity = 100;
    int D[capacity]={}, size;
    int Ps[capacity]={}, PCount,
        Cs[capacity]={}, CCount;
    init("D.txt", D, size);
    specialDisplay("Read from file Data Ds: ", D, size);
    segregatePrimesComposites(D, size, Ps, PCount, Cs, CCount);
    specialDisplay("Prime numbers array Ps: ", Ps, PCount);
    specialDisplay("Composite numbers array Cs: ", Cs, CCount);
    replacePsFollowedByCs(D, Ps, PCount, Cs, CCount);
    specialDisplay("Replaced Array - New Ds: ", D, size);
    return 0;
}

Exercise 3: Segregating fruits (mangoes, bananas, and apples)

We have to read and segregate the three different letters representing three fruits. We have b for a banana, m for a mango, and a for an apple. Segregate the values in such a way that all values of b come in the beginning and are followed by the m values and then the a values.

Sample input:

b m m m a a b a m a m b b b a

Sample output:

Segregated Fruits: 
Bananas: b b b b b 
Mangoes: m m m m m 
Apples:  a a a a a

Segregated Array: b b b b b m m m m m a a a a a

The code would be the same as the one given above, but you’ll add Bs (bananas), Ms (Mangoes), and As (Apples) array. In the segregateBsMsAs() function, check for the bananas, mangoes, and apples, and save in these arrays.

Here, we need to work with the code as we did before but with three arrays and their counts…

Write your solution here:

C++
void init(const char name[ ], char D[ ], int &size);
void specialDisplay(const char Msg[ ], char A[ ], int size);
// Assume, you have these implementations available
void segregateBsMsAs(char D[ ], int size, char Bs[ ], int &BCount, char Ms[ ], int &MCount, char As[ ], int &ACount)
{
    BCount = MCount = ACount = 0;
    
    int bi = 0, mi = 0, ai=0;
    // Write your code here
    
}
void replaceBs_Ms_As(char D[ ], char Bs[ ], int BCount, char Ms[ ], int MCount, char A[ ], int ACount)
{
    // Write your code here
    
}
int main()
{
    const int capacity = 100;
    char D[capacity]={};
    char Bs[capacity], Ms[capacity], As[capacity]; 
    int size, BCount,MCount,ACount;
    
    init("D.txt", D, size);
    specialDisplay("Read from file Data Ds: ", D, size);
    segregateBsMsAs(D, size, Bs, BCount, Ms, MCount, As, ACount);
    specialDisplay("Bs: ", Bs, BCount);
    specialDisplay("Ms: ", Ms, MCount);
    specialDisplay("As: ", As, ACount);
    replaceBs_Ms_As( D,  Bs,  BCount,  Ms,  MCount,  As,  ACount);
    specialDisplay("New Arrangement of fruits Ds: ", D, size);
    return 0;
}