Thread: Finding minimum number of swaps to sort a binary array in non-decreasing order

Hello,

I wrote a recursive function that returns the minimum
number of swaps required to sort a binary array in a non-decreasing order.
The swaps don't need to be adjacent, so for this example:

Code:

{1,0,0,0,1,0,1}

the output is 1.

The function gets as an input the address of the array and it's size.

After some corrections, I finally ran some different examples and now it seems like it's working fine.

Problem is, I mostly did it by intuition and I'm not completely sure if
it will always work.

The main idea I used is comparing the number of swaps required
for the array without the last element against without the first element, and returning the greater one.

If the number is equal on both sides, then I used a more complicated condition that increases the number by 1 if necessary.
That condition is the whole key of the recursion which I'm not
sure about.

So, If anyone has a good logical / mathematical explanation for this I would love to hear it

There's my function:

Code:

#include <stdio.h>
int FindMinSwitches(int a[], int n);


int main()
{
    int a[] = {1,0,0,0,1,0,1};


    printf("%d\n",FindMinSwitches(a, 7));


    return 0;
}


int FindMinSwitches(int a[], int n)
{
    int min_last = 0;
    int min_first = 0;
    int total_min = 0;




    if ((n == 1)||(n == 0)) {
        return 0;
    }


    if (n == 2) {
     return 0 + (a[0] > a[1]);
    }


    min_last = FindMinSwitches(a, n-1);
    min_first = FindMinSwitches(a+1,n-1);


    total_min = min_first > min_last ? min_first:min_last;


    if(min_first == min_last) {
        if ((a[0]==1)&&(a[n-1]==0)&&(FindMinSwitches(a+min_first,n-1-min_first)==1)) {
        total_min++;
        }
    }
    return total_min;
}

I'm inclined to count the number of 0s (call this N), then count the number of 1s (call this M) in the first N elements of the array. M is the minimum number of swaps required. This is more of an iterative algorithm than a recursive one though.