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)
Due to Naveen for suggesting this technique.
1) Rely the variety of 0s. So let’s perceive with an instance we now have an array arr = [0, 1, 0, 1, 0, 0, 1] the dimensions of the array is 7 now we’ll traverse all the array and discover out the variety of zeros within the array, On this case the variety of zeros is 4 so now we are able to simply get the variety of Ones within the array by Array Size – Quantity Of Zeros.
2) As soon as we now have counted, we are able to fill the array first we’ll put the zeros after which ones (we are able to get variety of ones by utilizing above components).
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
void segregate0and1(int arr[], int n)
{
int rely = 0;
for (int i = 0; i < n; i++)
if (arr[i] == 0)
rely++;
for (int i = 0; i < rely; i++)
arr[i] = 0;
for (int i = rely; 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 major()
{
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 rely = 0;
for (int i = 0; i < n; i++)
if (arr[i] == 0)
rely++;
for (int i = 0; i < rely; i++)
arr[i] = 0;
for (int i = rely; 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 major()
{
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 rely = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
rely++;
}
for (int i = 0; i < rely; i++)
arr[i] = 0;
for (int i = rely; 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 major(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) :
rely = 0
for i in vary(0, n) :
if (arr[i] == 0) :
rely = rely + 1
for i in vary(0, rely) :
arr[i] = 0
for i in vary(rely, 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 rely = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
rely++;
}
for (int i = 0; i < rely; i++)
arr[i] = 0;
for (int i = rely; 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 Primary()
{
int []arr = new int[]{ 0, 1, 0, 1, 1, 1 };
int n = arr.Size;
segregate0and1(arr, n);
print(arr, n);
}
}
|
PHP
<?php
operate segregate0and1(&$arr, $n)
{
$rely = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] == 0)
$rely++;
}
for ($i = 0; $i < $rely; $i++)
$arr[$i] = 0;
for ($i = $rely; $i < $n; $i++)
$arr[$i] = 1;
}
operate 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>
operate segregate0and1(arr, n)
{
let rely = 0;
for (let i = 0; i < n; i++) {
if (arr[i] == 0)
rely++;
}
for (let i = 0; i < rely; i++)
arr[i] = 0;
for (let i = rely; i < n; i++)
arr[i] = 1;
}
operate 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 House: O(1)
Methodology 1 traverses the array two occasions. Methodology 2 does the identical in a single go.
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) Maintain incrementing index left whereas there are 0s at it
b) Maintain decrementing index proper whereas there are 1s at it
c) If left < proper then trade 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 major()
{
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 major()
{
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 major(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 Primary()
{
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
operate 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>
operate 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 House: O(1)
One other strategy :
1. Take two pointer type0(for factor 0) ranging from starting (index = 0) and type1(for factor 1) ranging from finish (index = array.length-1).
Initialize type0 = 0 and type1 = array.length-1
2. It’s supposed to Put 1 to the suitable aspect of the array. As soon as it’s executed, then 0 will certainly in the 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 major()
{
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 major()
{
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 major(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 Primary(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
operate 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>
operate 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 House: O(1)
// Thanks san4net for suggesting this technique.
Please write feedback in case you discover any of the above algorithms/code incorrect, or a greater option to clear up the identical drawback.