algorithm - Given an array of 0 and 1, find minimum no. of swaps to bring all 1s together (only adjacent swaps allowed)

Question

If given an array of 1's and 0's, what's good algorithm to show the minimum number of adjacent swaps needed to group all of the 1's together. The 1's don't need to be grouped at any specific place in the array. They just need to be grouped in whatever place provides for the minimum number of adjacent swaps.

For example, if the array looks like this...

1,0,0,1,1,0,1

...the minimum number of adjacent swaps would be 3, because you'd center on index 4 and do the following swaps:

1. Swap indices 0 and 1, resulting in: 0,1,0,1,1,0,1

2. Swap indices 1 and 2, resulting in: 0,0,1,1,1,0,1

3. Swap indices 5 and 6, resulting in: 0,0,1,1,1,1,0

Anyone have a good algorithm for finding the minimum number of adjacent swaps for any array of 1's and 0's?

Answer 1

UPDATED:

The algorithm determines center by just getting an array of all indices of 1's. The center of that array will always hold the center index. Much faster.

oneIndices = array of indices of all 1's in the input
middleOfOnesIndices = round(oneIndices.length/2)-1    // index to the center index
minimumSwaps = 0
foreach index i of oneIndices
    minimumSwaps += aboluteValue(oneIndices[middleOfOneIndices]-oneIndices[i])-absoluteValue(middleOfOneIndices-i);

Here's a fiddle to see it in action:

https://jsfiddle.net/3pmwrk0d/6/

This was a fun one. Thanks for the question.