Given a binary array, the minimum number of adjacent swaps required to make it sorted

There are different methods that can be used to minimize the number of swaps required between adjacent elements to obtain a sorted array. The given output array contains only two types of elements i.e. 0 and 1. We will discuss two different ways to solve this problem, where the first solution uses extra space to store the number of zeros, while the second solution only uses constant space.

Problem Statement

We are given an array containing only two elements, 0 and 1. Our goal is to find the minimum number of swaps required to sort a given binary array.

The Chinese translation of

Example

is:

Example

Given Array: [1, 1, 0, 0, 0, 1, 0]
Result: 9 swaps required

The Chinese translation of

Explanation

is:

Explanation

Swap 1: [0, 1, 1, 0, 0, 0, 0]
Swap 2: [0, 1, 0, 1, 0, 0, 0]
Swap 3: [0, 1, 0, 0, 1, 0, 0]
Swap 4: [0, 1, 0, 0, 0, 1, 0]
Swap 5: [0, 1, 0, 0, 0, 0, 1]
Swap 6: [0, 0, 1, 0, 0, 0, 1]
Swap 7: [0, 0, 0, 1, 0, 0, 1]
Swap 8: [0, 0, 0, 0, 1, 0, 1]
Swap 9: [0, 0, 0, 0, 0, 1, 1]

Now let us discuss a simple way to solve this problem.

method one

In this method we will count the total number of 0s and 1s, we can do this by counting the number of 0s that appear after each 1 and then add them up. As we know, all the 1's will be at the far right of the array and all the 0's will be at the far left of the array, after sorting. This means, we have to swap every 1 in the array with every 0 to its right. The number of swaps required for each element in the array will be the total number of 0s that appear to its right in the array. We'll continue adding the total number of 0's that appear on the left for each 1 to get the required number of swaps.

The Chinese translation of

Example

is:

Example

In the example below, we create a binary array of seven numbers. We find the minimum number of neighbor swaps required to sort the array using the method above.

#include <bits/stdc++.h>
using namespace std;

// this function calculates the minimum number of swaps
int minimum_number_of_swaps(int given_array[], int nums){
   int Number_of_zeroes[nums];
   memset( Number_of_zeroes, 0, sizeof(Number_of_zeroes));
   int iterator, number = 0;
   Number_of_zeroes[nums - 1] = 1 - given_array[nums - 1];
   for (iterator = nums - 2; iterator >= 0; iterator--) {
      Number_of_zeroes[iterator] = Number_of_zeroes[iterator + 1];
      if (given_array[iterator] == 0)
      Number_of_zeroes[iterator]++;
   }
   for (iterator = 0; iterator < nums; iterator++) {
      if (given_array[iterator] == 1)
      number += Number_of_zeroes[iterator];
   }
   return number;
}
// main code goes from here
int main(){
   int given_array[] = { 1, 1, 0, 0, 0, 1, 0 };
   int nums = sizeof(given_array) / sizeof(given_array[0]);
   cout  << " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(given_array, nums);
   return 0;
}

Output

When you run the above C program, it will produce the following output -

Minimum number of swaps required to sort the given binary array is 9

The time complexity of this method - Since we iterate n times in a loop, the time complexity is: O(n)

Space Complexity - Since we use an extra array to store the number of zeros, the space complexity of this method is O(n)

Now let's look at a better and more efficient solution to the same problem. Our new solution saves memory as it does not take up any additional space.

Method Two

In this approach, we will minimize the auxiliary space to a constant space. Instead of reading the array from the beginning, we will iterate from the end and count the number of all zeros we encounter. If we get a 1, the number of swaps required to put that 1 in its sorted position is the number of zeros encountered before it.

The Chinese translation of

Example

is:

Example

The following is the C implementation of the above method -

#include <iostream>
using namespace std;

// this function finds out the least number of swaps needed
int minimum_number_of_swaps(int nums[], int number){
   int c = 0;
   int zeros_unplaced = 0;
   for(int iterator=number-1;iterator>=0;iterator--){
      if(nums[iterator] == 0)
      zeros_unplaced += 1;
      if(nums[iterator] == 1)
      c += zeros_unplaced;
   }
   return c;
}
// Main code goes here
int main(){
   int nums[] = { 1, 1, 0, 0, 0, 1, 0 };
   cout<< " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(nums, 7);
   return 0;
}

Output

When you run the above C program, it will produce the following output -

Minimum number of swaps required to sort the given binary array is 9

The time complexity of this method - Since we iterate n times in a loop, the time complexity is: O(n)

Space Complexity - Since we are not using any extra space, the space complexity is linear, i.e. O(1).

In this article, we discussed two methods of calculating the minimum number of swaps required to sort an array containing only 0s and 1s. In the first approach, we used an extra array to store the solution for each step, while in the second approach, we did it in constant space, resulting in better space complexity.

The above is the detailed content of Given a binary array, the minimum number of adjacent swaps required to make it sorted. For more information, please follow other related articles on the PHP Chinese website!