Minimum adjacent swaps required to Sort Binary array
Last Updated :
18 Feb, 2023
Given a binary array, task is to sort this binary array using minimum swaps. We are allowed to swap only adjacent elements
Examples:
Input : [0, 0, 1, 0, 1, 0, 1, 1]
Output : 3
1st swap : [0, 0, 1, 0, 0, 1, 1, 1]
2nd swap : [0, 0, 0, 1, 0, 1, 1, 1]
3rd swap : [0, 0, 0, 0, 1, 1, 1, 1]
Input : Array = [0, 1, 0, 1, 0]
Output : 3
Approach: This can be done by finding number of zeroes to the right side of every 1 and add them. In order to sort the array every one always has to perform a swap operation with every zero on its right side. So the total number of swap operations for a particular 1 in array is the number of zeroes on its right hand side. Find the number of zeroes on right side for every one i.e. the number of swaps and add them all to obtain the total number of swaps.
Steps to solve this problem:
1. Declare an integer array noOfZeroes of size n and initialize it with zeros using memset function.
2. Initialize a variable count to keep track of the total number of swaps required.
3. Initialize another variable i to traverse the array from the end.
4. Calculate the number of zeroes on the right side of every one and store it in the noOfZeroes array. This is done using a loop which starts from the second last element of the input array and goes till the first element. For every iteration, the value of noOfZeroes[i] is updated with the value of noOfZeroes[i+1]. If the current element of the input array is 0, the value of noOfZeroes[i] is incremented.
5. A loop is run over the input array to count the total number of swaps required. For every iteration, if the current element of the input array is 1, the value of count is incremented by noOfZeroes[i].
6. The function returns the value of count, which represents the minimum number of swaps required to make all ones together.
Implementation :
C++
#include <bits/stdc++.h>
using namespace std;
int findMinSwaps(int arr[], int n)
{
int noOfZeroes[n];
memset(noOfZeroes, 0, sizeof(noOfZeroes));
int i, count = 0;
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--) {
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
for (i = 0; i < n; i++) {
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
int main()
{
int arr[] = { 0, 0, 1, 0, 1, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinSwaps(arr, n);
return 0;
}
|
Java
class gfg {
static int findMinSwaps(int arr[], int n)
{
int noOfZeroes[] = new int[n];
int i, count = 0;
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
public static void main(String args[])
{
int ar[] = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(findMinSwaps(ar, ar.length));
}
}
|
Python3
def findMinSwaps(arr, n) :
noOfZeroes = [0] * n
count = 0
noOfZeroes[n - 1] = 1 - arr[n - 1]
for i in range(n-2, -1, -1) :
noOfZeroes[i] = noOfZeroes[i + 1]
if (arr[i] == 0) :
noOfZeroes[i] = noOfZeroes[i] + 1
for i in range(0, n) :
if (arr[i] == 1) :
count = count + noOfZeroes[i]
return count
arr = [ 0, 0, 1, 0, 1, 0, 1, 1 ]
n = len(arr)
print (findMinSwaps(arr, n))
|
C#
using System;
class GFG {
static int findMinSwaps(int []arr, int n)
{
int []noOfZeroes = new int[n];
int i, count = 0;
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
public static void Main()
{
int []ar = { 0, 0, 1, 0, 1,
0, 1, 1 };
Console.WriteLine(
findMinSwaps(ar, ar.Length));
}
}
|
PHP
<?php
function findMinSwaps($arr, $n)
{
$noOfZeroes[$n] = array();
$noOfZeroes = array_fill(0, $n, true);
$count = 0;
$noOfZeroes[$n - 1] = 1 - $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
{
$noOfZeroes[$i] = $noOfZeroes[$i + 1];
if ($arr[$i] == 0)
$noOfZeroes[$i]++;
}
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] == 1)
$count += $noOfZeroes[$i];
}
return $count;
}
$arr = array( 0, 0, 1, 0, 1, 0, 1, 1 );
$n = sizeof($arr);
echo findMinSwaps($arr, $n);
?>
|
Javascript
<script>
function findMinSwaps(arr, n)
{
let noOfZeroes = [];
let i, count = 0;
noOfZeroes[n - 1] = 1 - arr[n - 1];
for (i = n - 2; i >= 0; i--)
{
noOfZeroes[i] = noOfZeroes[i + 1];
if (arr[i] == 0)
noOfZeroes[i]++;
}
for (i = 0; i < n; i++)
{
if (arr[i] == 1)
count += noOfZeroes[i];
}
return count;
}
let ar = [ 0, 0, 1, 0, 1, 0, 1, 1 ];
document.write(findMinSwaps(ar, ar.length));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(n)
Space Optimized Solution: An auxiliary space is not needed. We just need to start reading the list from the back and keep track of number of zeros we encounter. If we encounter a 1 the number of zeros is the number of swaps needed to put the 1 in correct place.
Implementation:
C++
#include <iostream>
using namespace std;
int minswaps(int arr[], int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for(int index=n-1;index>=0;index--)
{
if(arr[index] == 0)
num_unplaced_zeros += 1;
if(arr[index] == 1)
count += num_unplaced_zeros;
}
return count;
}
int main()
{
int arr[] = {0, 0, 1, 0, 1, 0, 1, 1};
cout<<minswaps(arr, 8);
return 0;
}
|
Java
import java.io.*;
class GFG {
public static int minswaps(int arr[], int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for (int index = n - 1; index >= 0; index--)
{
if (arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
public static void main(String[] args)
{
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(minswaps(arr, 8));
}
}
|
Python3
def minswaps(arr):
count = 0
num_unplaced_zeros = 0
for index in range(len(arr)-1, -1, -1):
if arr[index] == 0:
num_unplaced_zeros += 1
else:
count += num_unplaced_zeros
return count
arr = [0, 0, 1, 0, 1, 0, 1, 1]
print(minswaps(arr))
|
C#
using System;
class GFG {
static int minswaps(int[] arr, int n)
{
int count = 0;
int num_unplaced_zeros = 0;
for (int index = n - 2; index >= 0; index--)
{
if (arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
static void Main() {
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
Console.WriteLine(minswaps(arr, 8));
}
}
|
Javascript
<script>
function minswaps(arr, n)
{
var count = 0;
var num_unplaced_zeros = 0;
for(var index = n - 1; index >= 0; index--)
{
if(arr[index] == 0)
num_unplaced_zeros += 1;
else
count += num_unplaced_zeros;
}
return count;
}
var arr = [0, 0, 1, 0, 1, 0, 1, 1];
document.write( minswaps(arr, 8));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...