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

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    6

    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;
    }
    Last edited by ido.r; 07-04-2019 at 05:19 AM. Reason: missing details

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,852
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2019
    Posts
    6
    Indeed it is a much simpler solution,
    but I'll confess that I've got an exam next week and I wanted to practice some recursive thinking.
    If you also have an explanation for why my suggested function is correct / incorrect I'll be very glad

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help finding the minimum value of an array
    By Kevin Nguyen in forum C Programming
    Replies: 5
    Last Post: 09-09-2013, 11:55 PM
  2. Finding maximum and minimum number in 2D array
    By wonderwall in forum C Programming
    Replies: 4
    Last Post: 10-23-2011, 10:21 PM
  3. Finding the minimum value in an array?
    By kabuatama in forum C Programming
    Replies: 8
    Last Post: 02-18-2006, 01:45 PM
  4. finding non-zero minimum in array
    By xstudent in forum C Programming
    Replies: 8
    Last Post: 12-16-2002, 03:58 AM
  5. finding minimum in array
    By xstudent in forum C# Programming
    Replies: 3
    Last Post: 12-15-2002, 12:23 AM

Tags for this Thread