Given an array containing 0 & 1 only, You have only 1 operation i.e. you can swap theadjacent elements in the array. Find the minimum number of operationsrequired to sort the given input array.

A = (0,0,1,0,1,0,1,1)

A = (0,0,1,0,1,0,1,1)

Min Operations: 3.

Approach:

Let's start with some of the trivial test cases.

(1,0) -- Number of swaps = 1

(1,1,0) -- Number of swaps = 2

(1,1,0,0) -- Number of swaps = 4

So an important observation comes that given an array of the type

(1, 1, 1, ... n times, 0, 0, 0, .. m times)

Number of swaps = n*m (This is based on the fact that each 0 has to be pushed(swapped) back m number of time)

So iterate over the array and keep track of the 1's encountered, whenever we hit a 0 we add the result(number of swaps) with the number of 1's encountered so far(as 0 has to be swapped with each of them order to reach a configuration like (0,0,..., 1, 1, 1...))

Now the piece of code will look like

Approach:

Let's start with some of the trivial test cases.

(1,0) -- Number of swaps = 1

(1,1,0) -- Number of swaps = 2

(1,1,0,0) -- Number of swaps = 4

So an important observation comes that given an array of the type

(1, 1, 1, ... n times, 0, 0, 0, .. m times)

Number of swaps = n*m (This is based on the fact that each 0 has to be pushed(swapped) back m number of time)

So iterate over the array and keep track of the 1's encountered, whenever we hit a 0 we add the result(number of swaps) with the number of 1's encountered so far(as 0 has to be swapped with each of them order to reach a configuration like (0,0,..., 1, 1, 1...))

Now the piece of code will look like

int swapSort(int *a, int n) { int swaps = 0; int noOfOne = 0; for (i =0;i<n;i++) { if (a[i] == 1) noOfOne++; else swaps += noOfOne; } return swaps; }

This Java method will count the number of operations required to sort the given array:

ReplyDelete// 0,0,1,0,1,0,1,1

private static int noOfOperations(int[] arr) {

// This will hold the no of 1's that the current 0 will be swapped.

int ones = 0;

// Total no of swap operations performed

int noOfOps = 0;

int i = 0;

while (i < arr.length) {

if (arr[i] == 1) {

ones++;

}

if (arr[i] == 0) {

if (ones > 0) {

noOfOps += ones;

}

}

i++;

}

System.out.println("Number of operations = " + noOfOps);

return noOfOps;

}