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.

New Comment





Categories
Relative Post