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:

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;
}