Posted on by Kalkicode
Code Array

# Segregate 0s and 1s in an array

The given problem is to segregate the 0s and 1s in an array. Segregating means rearranging the array in such a way that all the 0s appear first, followed by all the 1s. The relative order of the 0s and 1s should be maintained during segregation.

## Problem Statement

Given an array containing only 0s and 1s, we need to rearrange the elements such that all 0s are grouped together at the beginning, and all 1s are grouped together at the end, while preserving the original order of 0s and 1s.

## Explanation with Example

Let's take an example array: [1, 0, 1, 0, 0, 1, 1, 0, 1]. After segregation, the array should become: [0, 0, 0, 0, 1, 1, 1, 1, 1]. All the 0s are together at the beginning, and all the 1s are together at the end.

## Standard Pseudocode

``````segregate_element(arr, size):
zero = 0
one = 0

for zero = 0 to size:
if arr[zero] == 0:
swap_element(arr, one, zero)
one = one + 1

return arr
``````

## Algorithm Explanation

1. The function `segregate_element` takes the array `arr` and its size `size` as input parameters.
2. It initializes two variables `zero` and `one` to keep track of the position of the 0s and 1s, respectively.
3. The loop runs from `zero = 0` to `size-1`.
4. For each element in the array, if it is equal to 0, we swap it with the element at the `one` position and increment the value of `one`.
5. This effectively moves all the 0s to the left side of the array while preserving their relative order.
6. After the loop completes, the array will be segregated, and we return the modified array.

## Code Solution

``````// C Program
// segregate 0s and 1s in an array
#include <stdio.h>
//Function which is swapping two array elements of given location
void swap_element(int arr[], int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int arr[], int size)
{
int zero = 0;
int one = 0;
//Just before the modifying array elements
printf("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one++;
}
}
//After modify array elements
printf("After Segregating zero and one \n");
display(arr, size);
printf("\n");
}
int main()
{
//Define array elements
int arr1[] = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = sizeof(arr1) / sizeof(arr1[0]);
segregate_element(arr1, size);
//Define array elements
int arr2[] = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = sizeof(arr2) / sizeof(arr2[0]);
segregate_element(arr2, size);
return 0;
}``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````/*
Java Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
void swap_element(int[] arr, int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("" + arr[i] + " ");
}
System.out.print("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int[] arr, int size)
{
int zero = 0;
int one = 0;
System.out.print("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one++;
}
}
System.out.print("After Segregating zero and one \n");
display(arr, size);
System.out.print("\n");
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define array elements 1 and 0s elements
int[] arr1 =  {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
int[] arr2 = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = arr2.length;
obj.segregate_element(arr2, size);
}
}``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````/*
C++ Program
Segregate 0s and 1s in an array
*/
#include<iostream>

using namespace std;
class MyArray
{
public:
//Function which is swapping two array elements of given location
void swap_element(int arr[], int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "" << arr[i] << " ";
}
cout << "\n";
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int arr[], int size)
{
int zero = 0;
int one = 0;
cout << "Before Segregating zero and one \n";
this->display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
this->swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one++;
}
}
cout << "After Segregating zero and one \n";
this->display(arr, size);
cout << "\n";
}
};
int main()
{
MyArray obj ;
int arr1[] = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.segregate_element(arr1, size);
int arr2[] = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = sizeof(arr2) / sizeof(arr2[0]);
obj.segregate_element(arr2, size);
return 0;
}``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````/*
C# Program
Segregate 0s and 1s in an array
*/
using System;
class MyArray
{
//Function which is swapping two array elements of given location
void swap_element(int[] arr, int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write("" + arr[i] + " ");
}
Console.Write("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int[] arr, int size)
{
int zero = 0;
int one = 0;
Console.Write("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; zero++)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one++;
}
}
Console.Write("After Segregating zero and one \n");
display(arr, size);
Console.Write("\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = arr1.Length;
obj.segregate_element(arr1, size);
int[] arr2 = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = arr2.Length;
obj.segregate_element(arr2, size);
}
}``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````<?php
/*
Php Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
function swap_element( & \$arr, \$i, \$j)
{
//Get i location element
\$temp = \$arr[\$i];
//set new values
\$arr[\$i] = \$arr[\$j];
\$arr[\$j] = \$temp;
}
//Function which is display array elements
function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "". \$arr[\$i] ." ";
}
echo "\n";
}
//Function which is separating given array elements of 0s and 1s
function segregate_element( & \$arr, \$size)
{
\$zero = 0;
\$one = 0;
echo "Before Segregating zero and one \n";
\$this->display(\$arr, \$size);
for (\$zero = 0; \$zero < \$size; ++\$zero)
{
if (\$arr[\$zero] == 0)
{
\$this->swap_element(\$arr, \$one, \$zero);
//visit to next location, incremented  location value by one
\$one++;
}
}
echo "After Segregating zero and one \n";
\$this->display(\$arr, \$size);
echo "\n";
}
}

function main()
{
\$obj = new MyArray();
//Define array elements 1 and 0s elements
\$arr1 = array(1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1);
\$size = count(\$arr1);
\$obj->segregate_element(\$arr1, \$size);
//Define array elements
\$arr2 = array(0, 1, 1, 0, 0, 0, 0, 1, 0, 1);
\$size = count(\$arr2);
\$obj->segregate_element(\$arr2, \$size);
}
main();``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````/*
Node Js Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
swap_element(arr, i, j)
{
//Get i location element
var temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("" + arr[i] + " ");
}
process.stdout.write("\n");
}
//Function which is separating given array elements of 0s and 1s
segregate_element(arr, size)
{
var zero = 0;
var one = 0;
process.stdout.write("Before Segregating zero and one \n");
this.display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
this.swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one++;
}
}
process.stdout.write("After Segregating zero and one \n");
this.display(arr, size);
process.stdout.write("\n");
}
}

function main()
{
var obj = new MyArray();
//Define array elements 1 and 0s elements
var arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1];
var size = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
var arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1];
size = arr2.length;
obj.segregate_element(arr2, size);
}
main();``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````#   Python 3 Program
#   Segregate 0s and 1s in an array

class MyArray :
# Function which is swapping two array elements of given location
def swap_element(self, arr, i, j) :
# Get i location element
temp = arr[i]
# set new values
arr[i] = arr[j]
arr[j] = temp

# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print("", arr[i] ," ", end = "")
i += 1

print("\n", end = "")

# Function which is separating given array elements of 0s and 1s
def segregate_element(self, arr, size) :
zero = 0
one = 0
print("Before Segregating zero and one \n", end = "")
self.display(arr, size)
while (zero < size) :
if (arr[zero] == 0) :
self.swap_element(arr, one, zero)
# visit to next location, incremented  location value by one
one += 1

zero += 1

print("After Segregating zero and one \n", end = "")
self.display(arr, size)
print("\n", end = "")

def main() :
obj = MyArray()
# Define array elements 1 and 0s elements
arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
size = len(arr1)
obj.segregate_element(arr1, size)
# Define array elements
arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]
size = len(arr2)
obj.segregate_element(arr2, size)

if __name__ == "__main__": main()``````

#### Output

``````Before Segregating zero and one
1   1   0   1   0   0   1   1   0   0   0   0   0   1
After Segregating zero and one
0   0   0   0   0   0   0   0   1   1   1   1   1   1

Before Segregating zero and one
0   1   1   0   0   0   0   1   0   1
After Segregating zero and one
0   0   0   0   0   0   1   1   1   1
``````
``````#   Ruby Program
#   Segregate 0s and 1s in an array

class MyArray

# Function which is swapping two array elements of given location
def swap_element(arr, i, j)

# Get i location element
temp = arr[i]
# set new values
arr[i] = arr[j]
arr[j] = temp
end
# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print("", arr[i] ," ")
i += 1
end
print("\n")
end
# Function which is separating given array elements of 0s and 1s
def segregate_element(arr, size)

zero = 0
one = 0
print("Before Segregating zero and one \n")
self.display(arr, size)
while (zero < size)

if (arr[zero] == 0)

self.swap_element(arr, one, zero)
# visit to next location, incremented  location value by one
one += 1
end
zero += 1
end
print("After Segregating zero and one \n")
self.display(arr, size)
print("\n")
end
end
def main()

obj = MyArray.new()
# Define array elements 1 and 0s elements
arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
size = arr1.length
obj.segregate_element(arr1, size)
# Define array elements
arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]
size = arr2.length
obj.segregate_element(arr2, size)
end
main()``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1

``````
``````/*
Scala Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
def swap_element(arr: Array[Int], i: Int, j: Int): Unit = {
//Get i location element
var temp: Int = arr(i);
//set new values
arr(i) = arr(j);
arr(j) = temp;
}
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("" + arr(i) + " ");
i += 1;
}
print("\n");
}
//Function which is separating given array elements of 0s and 1s
def segregate_element(arr: Array[Int], size: Int): Unit = {
var zero: Int = 0;
var one: Int = 0;
print("Before Segregating zero and one \n");
display(arr, size);
while (zero < size)
{
if (arr(zero) == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented  location value by one
one += 1;
}
zero += 1;
}
print("After Segregating zero and one \n");
display(arr, size);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array elements 1 and 0s elements
var arr1: Array[Int] = Array(1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1);
var size: Int = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
var arr2: Array[Int] = Array(0, 1, 1, 0, 0, 0, 0, 1, 0, 1);
size = arr2.length;
obj.segregate_element(arr2, size);
}
}``````

#### Output

``````Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1

Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
``````
``````/*
Swift Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
func swap_element(_ arr: inout[Int], _ i: Int, _ j: Int)
{
//Get i location element
let temp: Int = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("", arr[i] ," ", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Function which is separating given array elements of 0s and 1s
func segregate_element(_ arr: inout[Int], _ size: Int)
{
var zero: Int = 0;
var one: Int = 0;
print("Before Segregating zero and one \n", terminator: "");
self.display(arr, size);
while (zero < size)
{
if (arr[zero] == 0)
{
self.swap_element(&arr, one, zero);
//visit to next location, incremented  location value by one
one += 1;
}
zero += 1;
}
print("After Segregating zero and one \n", terminator: "");
self.display(arr, size);
print("\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array elements 1 and 0s elements
var arr1: [Int] = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1];
var size: Int = arr1.count;
obj.segregate_element(&arr1, size);
//Define array elements
var arr2: [Int] = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1];
size = arr2.count;
obj.segregate_element(&arr2, size);
}
main();``````

#### Output

``````Before Segregating zero and one
1   1   0   1   0   0   1   1   0   0   0   0   0   1
After Segregating zero and one
0   0   0   0   0   0   0   0   1   1   1   1   1   1

Before Segregating zero and one
0   1   1   0   0   0   0   1   0   1
After Segregating zero and one
0   0   0   0   0   0   1   1   1   1
``````

## Resultant Output Explanation

Let's analyze the output for the two input arrays provided in the code:

Input 1 (arr1): [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]

Before Segregating zero and one: [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1] After Segregating zero and one: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]

Input 2 (arr2): [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]

Before Segregating zero and one: [0, 1, 1, 0, 0, 0, 0, 1, 0, 1] After Segregating zero and one: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1]

## Time Complexity of the Code

The time complexity of the code is O(n) where 'n' is the size of the input array. The segregation process involves traversing the array once and performing a constant-time operation (swapping) for each element, resulting in a linear time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post