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