You’re given an array of 0s and 1s in random order. Segregate 0s on left aspect and 1s on proper aspect of the array [Basically you have to sort the array]. Traverse array solely as soon as.
Enter array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Methodology 1 (Rely 0s or 1s)
Because of Naveen for suggesting this methodology.
1) Rely the variety of 0s. So let’s perceive with an instance we have now an array arr = [0, 1, 0, 1, 0, 0, 1] the dimensions of the array is 7 now we are going to traverse the complete array and discover out the variety of zeros within the array, On this case the variety of zeros is 4 so now we will simply get the variety of Ones within the array by Array Size – Quantity Of Zeros.
2) As soon as we have now counted, we will fill the array first we are going to put the zeros after which ones (we will get variety of ones through the use of above formulation).
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void segregate0and1(int arr[], int n)
{
int depend = 0;
for (int i = 0; i < n; i++)
if (arr[i] == 0)
depend++;
for (int i = 0; i < depend; i++)
arr[i] = 0;
for (int i = depend; i < n; i++)
arr[i] = 1;
}
void print(int arr[], int n)
{
cout << "Array after segregation is ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int essential()
{
int arr[] = { 0, 1, 0, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
segregate0and1(arr, n);
print(arr, n);
return 0;
}
|
C
#embrace <stdio.h>
void segregate0and1(int arr[], int n)
{
int depend = 0;
for (int i = 0; i < n; i++)
if (arr[i] == 0)
depend++;
for (int i = 0; i < depend; i++)
arr[i] = 0;
for (int i = depend; i < n; i++)
arr[i] = 1;
}
void print(int arr[], int n)
{
printf("Array after segregation is ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}
int essential()
{
int arr[] = { 0, 1, 0, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
segregate0and1(arr, n);
print(arr, n);
return 0;
}
|
Java
import java.io.*;
public class GFG {
static void segregate0and1(int arr[], int n)
{
int depend = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
depend++;
}
for (int i = 0; i < depend; i++)
arr[i] = 0;
for (int i = depend; i < n; i++)
arr[i] = 1;
}
static void print(int arr[], int n)
{
System.out.print("Array after segregation is ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void essential(String[] args)
{
int arr[] = new int[]{ 0, 1, 0, 1, 1, 1 };
int n = arr.size;
segregate0and1(arr, n);
print(arr, n);
}
}
|
Python3
def segregate0and1(arr, n) :
depend = 0
for i in vary(0, n) :
if (arr[i] == 0) :
depend = depend + 1
for i in vary(0, depend) :
arr[i] = 0
for i in vary(depend, n) :
arr[i] = 1
def print_arr(arr , n) :
print( "Array after segregation is ",finish = "")
for i in vary(0, n) :
print(arr[i] , finish = " ")
arr = [ 0, 1, 0, 1, 1, 1 ]
n = len(arr)
segregate0and1(arr, n)
print_arr(arr, n)
|
C#
utilizing System;
class GFG {
static void segregate0and1(int []arr, int n)
{
int depend = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
depend++;
}
for (int i = 0; i < depend; i++)
arr[i] = 0;
for (int i = depend; i < n; i++)
arr[i] = 1;
}
static void print(int []arr, int n)
{
Console.WriteLine("Array after segregation is ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
public static void Most important()
{
int []arr = new int[]{ 0, 1, 0, 1, 1, 1 };
int n = arr.Size;
segregate0and1(arr, n);
print(arr, n);
}
}
|
PHP
<?php
perform segregate0and1(&$arr, $n)
{
$depend = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] == 0)
$depend++;
}
for ($i = 0; $i < $depend; $i++)
$arr[$i] = 0;
for ($i = $depend; $i < $n; $i++)
$arr[$i] = 1;
}
perform toprint(&$arr , $n)
{
echo ("Array after segregation is ");
for ($i = 0; $i < $n; $i++)
echo ( $arr[$i] . " ");
}
$arr = array(0, 1, 0, 1, 1, 1 );
$n = sizeof($arr);
segregate0and1($arr, $n);
toprint($arr, $n);
?>
|
Javascript
<script>
perform segregate0and1(arr, n)
{
let depend = 0;
for (let i = 0; i < n; i++) {
if (arr[i] == 0)
depend++;
}
for (let i = 0; i < depend; i++)
arr[i] = 0;
for (let i = depend; i < n; i++)
arr[i] = 1;
}
perform print(arr, n)
{
doc.write("Array after segregation is ");
for (let i = 0; i < n; i++)
doc.write(arr[i] + " ");
}
let arr = [ 0, 1, 0, 1, 1, 1 ];
let n = arr.size;
segregate0and1(arr, n);
print(arr, n);
</script>
|
Output
Array after segregation is 0 0 1 1 1 1
Time Complexity : O(2n) ≅ O(n)
Auxiliary Area: O(1)
Methodology 1 traverses the array two occasions. Methodology 2 does the identical in a single cross.
Methodology 1 has time complexity of O(2n) and Methodology 2 has time complexity of O(n)
Methodology 2 (Use two indexes to traverse)
Preserve two indexes. Initialize the primary index left as 0 and second index proper as n-1.
Do following whereas left < proper
a) Hold incrementing index left whereas there are 0s at it
b) Hold decrementing index proper whereas there are 1s at it
c) If left < proper then alternate arr[left] and arr[right]
Implementation:
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void segregate0and1(int arr[], int measurement)
{
int left = 0, proper = size-1;
whereas (left < proper)
{
whereas (arr[left] == 0 && left < proper)
left++;
whereas (arr[right] == 1 && left < proper)
right--;
if (left < proper)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
int essential()
{
int arr[] = {0, 1, 0, 1, 1, 1};
int i, arr_size = sizeof(arr)/sizeof(arr[0]);
segregate0and1(arr, arr_size);
cout << "Array after segregation ";
for (i = 0; i < 6; i++)
cout << arr[i] << " ";
return 0;
}
|
C
#embrace<stdio.h>
void segregate0and1(int arr[], int measurement)
{
int left = 0, proper = size-1;
whereas (left < proper)
{
whereas (arr[left] == 0 && left < proper)
left++;
whereas (arr[right] == 1 && left < proper)
right--;
if (left < proper)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
int essential()
{
int arr[] = {0, 1, 0, 1, 1, 1};
int i, arr_size = sizeof(arr)/sizeof(arr[0]);
segregate0and1(arr, arr_size);
printf("Array after segregation ");
for (i = 0; i < 6; i++)
printf("%d ", arr[i]);
getchar();
return 0;
}
|
Java
import java.io.*;
public class Segregate
{
void segregate0and1(int arr[], int measurement)
{
int left = 0, proper = measurement - 1;
whereas (left < proper)
{
whereas (arr[left] == 0 && left < proper)
left++;
whereas (arr[right] == 1 && left < proper)
right--;
if (left < proper)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
public static void essential(String[] args)
{
Segregate seg = new Segregate();
int arr[] = new int[]{0, 1, 0, 1, 1, 1};
int i, arr_size = arr.size;
seg.segregate0and1(arr, arr_size);
System.out.print("Array after segregation is ");
for (i = 0; i < 6; i++)
System.out.print(arr[i] + " ");
}
}
|
Python
def segregate0and1(arr, measurement):
left, proper = 0, measurement-1
whereas left < proper:
whereas arr[left] == 0 and left < proper:
left += 1
whereas arr[right] == 1 and left < proper:
proper -= 1
if left < proper:
arr[left] = 0
arr[right] = 1
left += 1
proper -= 1
return arr
arr = [0, 1, 0, 1, 1, 1]
arr_size = len(arr)
print("Array after segregation")
print(segregate0and1(arr, arr_size))
|
C#
utilizing System;
class Segregate
{
void segregate0and1(int []arr, int measurement)
{
int left = 0, proper = measurement - 1;
whereas (left < proper)
{
whereas (arr[left] == 0 && left < proper)
left++;
whereas (arr[right] == 1 && left < proper)
right--;
if (left < proper)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
public static void Most important()
{
Segregate seg = new Segregate();
int []arr = new int[]{0, 1, 0, 1, 1, 1};
int i, arr_size = arr.Size;
seg.segregate0and1(arr, arr_size);
Console.WriteLine("Array after segregation is ");
for (i = 0; i < 6; i++)
Console.Write(arr[i] + " ");
}
}
|
PHP
<?php
perform segregate0and1(&$arr, $measurement)
{
$left = 0;
$proper = $measurement - 1;
whereas ($left < $proper)
{
whereas ($arr[$left] == 0 &&
$left < $proper)
$left++;
whereas ($arr[$right] == 1 &&
$left < $proper)
$proper--;
if ($left < $proper)
{
$arr[$left] = 0;
$arr[$right] = 1;
$left++;
$proper--;
}
}
}
$arr = array(0, 1, 0, 1, 1, 1);
$arr_size = sizeof($arr);
segregate0and1($arr, $arr_size);
printf("Array after segregation is ");
for ($i = 0; $i < 6; $i++)
echo ($arr[$i]. " ");
?>
|
Javascript
<script>
perform segregate0and1(arr, measurement)
{
let left = 0, proper = size-1;
whereas (left < proper)
{
whereas (arr[left] == 0 && left < proper)
left++;
whereas (arr[right] == 1 && left < proper)
right--;
if (left < proper)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
let arr = [0, 1, 0, 1, 1, 1];
let i, arr_size = arr.size;
segregate0and1(arr, arr_size);
doc.write("Array after segregation ");
for (i = 0; i < 6; i++)
doc.write(arr[i] + " ");
</script>
|
Output
Array after segregation 0 0 1 1 1 1
Time Complexity : O(n)
Auxiliary Area: O(1)
One other strategy :
1. Take two pointer type0(for component 0) ranging from starting (index = 0) and type1(for component 1) ranging from finish (index = array.length-1).
Initialize type0 = 0 and type1 = array.length-1
2. It’s meant to Put 1 to the suitable aspect of the array. As soon as it’s finished, then 0 will certainly in direction of the left aspect of the array.
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void segregate0and1(int arr[], int measurement)
{
int type0 = 0;
int type1 = measurement - 1;
whereas (type0 < type1) {
if (arr[type0] == 1) {
if (arr[type1] != 1)
swap(arr[type0], arr[type1]);
type1--;
}
else
type0++;
}
}
int essential()
{
int arr[] = { 0, 1, 0, 1, 1, 1 };
int i, arr_size = sizeof(arr) / sizeof(arr[0]);
segregate0and1(arr, arr_size);
cout << "Array after segregation is ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
return 0;
}
|
C
#embrace <stdio.h>
void segregate0and1(int arr[], int measurement)
{
int type0 = 0;
int type1 = measurement - 1;
whereas (type0 < type1) {
if (arr[type0] == 1) {
if (arr[type1] != 1) {
int temp = arr[type0];
arr[type0] = arr[type1];
arr[type1] = temp;
}
type1--;
}
else
type0++;
}
}
int essential()
{
int arr[] = { 0, 1, 0, 1, 1, 1 };
int i, arr_size = sizeof(arr) / sizeof(arr[0]);
segregate0and1(arr, arr_size);
printf("Array after segregation is ");
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
/**
Methodology for segregation 0 and 1 given enter array
*/
static void segregate0and1(int arr[])
{
int type0 = 0;
int type1 = arr.size - 1;
whereas (type0 < type1) {
if (arr[type0] == 1) {
if (arr[type1] != 1) {
arr[type1] = arr[type1] + arr[type0];
arr[type0] = arr[type1] - arr[type0];
arr[type1] = arr[type1] - arr[type0];
}
type1--;
}
else {
type0++;
}
}
}
public static void essential(String[] args)
{
int[] array = { 0, 1, 0, 1, 1, 1 };
segregate0and1(array);
for (int a : array) {
System.out.print(a + " ");
}
}
}
|
Python3
def segregate0and1(arr, measurement):
type0 = 0
type1 = measurement - 1
whereas(type0 < type1):
if(arr[type0] == 1):
if(arr[type1] != 1):
(arr[type0],
arr[type1]) = (arr[type1],
arr[type0])
type1 -= 1
else:
type0 += 1
arr = [0, 1, 0, 1, 1, 1]
arr_size = len(arr)
segregate0and1(arr, arr_size)
print("Array after segregation is",
finish = " ")
for i in vary(0, arr_size):
print(arr[i], finish = " ")
|
C#
utilizing System;
class GFG {
static void segregate0and1(int[] arr)
{
int type0 = 0;
int type1 = arr.Size - 1;
whereas (type0 < type1) {
if (arr[type0] == 1) {
if (arr[type1] != 1) {
arr[type1] = arr[type1] + arr[type0];
arr[type0] = arr[type1] - arr[type0];
arr[type1] = arr[type1] - arr[type0];
}
type1--;
}
else {
type0++;
}
}
}
public static void Most important(string[] args)
{
int[] array = new int[] { 0, 1, 0, 1, 1, 1 };
segregate0and1(array);
Console.Write("Array after segregation is ");
foreach(int a in array) { Console.Write(a + " "); }
}
}
|
PHP
<?php
perform segregate0and1(&$arr , $measurement)
{
$type0 = 0;
$type1 = $measurement - 1;
whereas($type0 < $type1)
{
if($arr[$type0] == 1)
{
if($arr[$type1] != 1)
{
$temp = $arr[$type0];
$arr[$type0] = $arr[$type1];
$arr[$type1] = $temp;
}
$type1--;
}
else
$type0++;
}
}
$arr = array(0, 1, 0, 1, 1, 1);
$arr_size = sizeof($arr);
segregate0and1($arr, $arr_size);
echo ("Array after segregation is ");
for ($i = 0; $i < $arr_size; $i++)
echo ($arr[$i] . " ");
?>
|
Javascript
<script>
perform segregate0and1(arr, measurement)
{
let type0 = 0;
let type1 = measurement - 1;
whereas (type0 < type1)
{
if (arr[type0] == 1)
{
if (arr[type1] != 1)
{
arr[type1] = arr[type1] + arr[type0];
arr[type0] = arr[type1] - arr[type0];
arr[type1] = arr[type1] - arr[type0];
}
type1--;
}
else
type0++;
}
}
let arr = [ 0, 1, 0, 1, 1, 1 ];
let i, arr_size = arr.size;
segregate0and1(arr, arr_size);
doc.write("Array after segregation is ");
for(i = 0; i < arr_size; i++)
doc.write(arr[i] + " ");
</script>
|
Output
Array after segregation is 0 0 1 1 1 1
Time complexity: O(n)
Auxiliary Area: O(1)
// Thanks san4net for suggesting this methodology.
Please write feedback for those who discover any of the above algorithms/code incorrect, or a greater strategy to resolve the identical drawback.
