4

I have an array of containing a mixture of 0s and 1s. I want to rearrange the contents of the array so that as many even positions in the array contain 0 and odd positions contain 1 as possible, subject to the constraint that the number of 0s and 1s are unchanged. This means that if the number of 0s exceeds the number of 1s or vice versa then there will a block at the end of the rearranged array consisting of all-0s or all-1s. How can I do this in one pass, modifying the array in place?

For example:

Input:  {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}
Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
Sunny
  • 57
  • 2
  • 2
    There're no questions here... (Ctrl+F finds no "?" characters in your question) typically we (on Stack Overflow) ask that you show what you've tried, and ask what you're having trouble with. See: http://tinyurl.com/so-hints – Chris Pfohl Mar 10 '11 at 17:46
  • 2
    I don't understand "leave them where they are" requirement. In your input number of 1s exceeds the number of 0s. So, what exactly did you leave "where they are"? – AnT stands with Russia Mar 10 '11 at 23:32
  • 1
    Your example has more 1's than 0's, but it does not leave everything where they are. – Adam Rosenfield Mar 10 '11 at 23:42

9 Answers9

4

You can just use the standard two-color sort algorithm for this; just edit the array references to map accesses to the first half of the array to even elements in your actual array, and accesses to the second half of the array to odd elements in your actual array (backwards). Basically, a[i] becomes (assuming size is even):

a[i < size/2 ? i * 2 : (size - i) * 2 - 1]
Jeremiah Willcock
  • 30,161
  • 7
  • 76
  • 78
  • Can you give me a reference to two-color sort algorithm? I haven't found it with google. – xanatos Mar 10 '11 at 18:23
  • @xanatos: See http://en.wikipedia.org/wiki/Quicksort#Complex_version; in your case, the pivot is 1 and you put things less than it at the beginning and things greater than or equal to it at the end. – Jeremiah Willcock Mar 10 '11 at 19:28
2
int a[10] = {1, 1, 0, 1, 1, 0, 1, 1, 1, 0};
int i;
int count_0 = 0;
int count_1 = 0;
for(i = 0; i < 10; i++)
{
  if(a[i] == 0)
  {
    if(count_1 > 0)
    {
      if(i % 2 == 0)
      {
        a[i-2*count_1+1] = 0;
        a[i] = 1;
        count_1--;
      }
      else
      {
        a[i-2*count_1] = 0;
        a[i] = 1;
      }
    }
    else
    {
      if(i % 2 == 0)
      count_0++;
    }
  }
  else
  {
    if(count_0 > 0)
    {
      if(i % 2 != 0)
      {
        a[i-2*count_0+1] = 1;
        a[i] = 0;
        count_0--;
      }
      else
      {
        a[i-2*count_0] = 1;
        a[i] = 0;
      }
    }
    else
    {
      if(i % 2 != 0)
      count_1++;
    }
  }
}
Em1
  • 1,077
  • 18
  • 38
ASHISH
  • 29
  • 1
  • 3
    Welcome to StackOverflow, as nice as this code looks it might be useful to get some commentary to help others understand it. – James Wood Dec 12 '12 at 11:54
2

I don't think it can be made in 1 pass, unless the "leave them where they are" means "it doesn't matter where they end up".

Here's my attempt with two passes :)

void zeroone(int *arr, size_t n) {
  int *ptr = arr;
  size_t nn = n;
  int s = 0;

  /* if the array has an odd number of elements
  ** the number of 0's is different then the number of 1's */    
  if (n % 2) return;

  /* 1st pass */
  while (nn--) s += *ptr++;

  /* if there are as many 0's as 1's */
  if (s+s == n) {
    /* 2nd pass */
    for (nn = 0; nn < n; nn += 2) {
      arr[nn] = 0;
      arr[nn + 1] = 1;
    }
  }
}
pmg
  • 106,608
  • 13
  • 126
  • 198
  • +1 Agree. You cannot know for sure until the end of first pass if it has to be "sorted", so the "sorting" cannot be performed in the first iteration. The only way to do it in a single iteration is to use a second array. – ruslik Mar 11 '11 at 00:57
2

Loop through the array, maintaining invariants for 3 variables and the array:

  • everything before pos has been sorted.
  • color is the color of the element that should be placed at pos.
  • everything between pos and next has the same color.
  • the array is a permutation of itself.

Anyway, it seems to work.

def odd_even_sort(xs):
    color = 0
    pos = 0
    next = pos + 1
    while next < len(xs):
        if xs[pos] == color:
            pos += 1
            if pos >= next:
                next = pos + 1
            color = not color
        elif xs[next] == color:
            xs[pos], xs[next] = xs[next], xs[pos]
            next += 1
            pos += 1
            color = not color
        else:
            next += 1

xs = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1]
odd_even_sort(xs)
print xs
antonakos
  • 8,261
  • 2
  • 31
  • 34
1

This can be done in single pass.

Here's another solution that uses single pass. The idea is to keep two indexes pos_0 and pos_1 which holds the location where the next 0 or 1 is to be placed in the array. i will be used to traverse through the array.

//
//array a[] and length are members of the class AlternateZeroAndOne
//
void AlternateZeroAndOne::sortArray()
{
    int pos_0 = 0;
    int pos_1 = 1;

    for (int i=0; i<length; ++i)
    {
        //
        // We have been waiting for a zero to be placed at the correct location.
        //
        if (pos_0 < pos_1)
        {
            if (a[i] == 0)
            {
                swap(pos_0, i);
                pos_0+=2;

                //
                // If we had a 1 already at the right place, increment pos_1.
                //
                if (a[pos_1] == 1)
                    pos_1+=2;
            }
        }

        //
        // We have been waiting for a one to be placed at the correct location.
        //
        else
        {
            if (a[i] == 1)
            {
                swap(pos_1, i);
                pos_1 += 2;

                //
                // If we had a 0 already at the right place, increment pos_0.
                //
                if (a[pos_0] == 0)
                    pos_0+=2;
            }
        }
    }
}
mthaha
  • 11
  • 2
1

This will do it. The result is different from the proposed output, but is equal to the rules given (the text of the problem doesn't include the word "sort", only that at the end you have to move all the 0 you can in even positions and the 1 you can in odd positions. You don't need to "compact" them). It's a little more complex to do it "compacting".

static void Main(string[] args)
{
    var input = new[] { 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1 };

    var lastEvenToMove = -1;
    var lastOddToMove = -1;

    for (int i = 0; i < input.Length; i++)
    {
        bool needEven = i % 2 == 0;
        bool isEven = input[i] == 0;

        if (needEven == isEven)
        {
            continue;
        }

        if (needEven)
        {
            if (lastEvenToMove != -1)
            {
                var old = input[lastEvenToMove];
                input[lastEvenToMove] = 1;
                input[i] = 0;
                lastEvenToMove = old;
            }
            else
            {
                input[i] = lastOddToMove;
                lastOddToMove = i;
            }
        }
        else
        {
            if (lastOddToMove != -1)
            {
                var old = input[lastOddToMove];
                input[lastOddToMove] = 0;
                input[i] = 1;
                lastOddToMove = old;
            }
            else
            {
                input[i] = lastEvenToMove;
                lastEvenToMove = i;
            }
        }
    }

    while (lastEvenToMove != -1)
    {
        var old = input[lastEvenToMove];
        input[lastEvenToMove] = 0;
        lastEvenToMove = old;
    }

    while (lastOddToMove != -1)
    {
        var old = input[lastOddToMove];
        input[lastOddToMove] = 1;
        lastOddToMove = old;
    }

    Console.WriteLine(@"{{{0}}}", String.Join(", ", input.Select(p => p.ToString())));
}

I keep a stack of the odds and a stack of the even elements that need moving, and I use these when I need an odd/even number. The two stacks are keeped in the input array, so no extra space (except the two "heads" of the two stacks, that are two extra integers). I think the worst case is O(1.5n) for time (for example all the elements are 1, half of the elements are "put" in the stack and then need resetting because there wasn't an empty space), and O(1) for space.

Output:

{0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1}
xanatos
  • 109,618
  • 12
  • 197
  • 280
1
#include<iostream>

using namespace std;

//////////////////////////////////////////

int a[]={1,1,0,1,0,1,1,1,0,1,0,1,0,0,0,0,1,1,1,1,0,0} ;


int main()
{

    int zero = 0, one = 1;
    int n = sizeof(a)/sizeof(*a);
    int i = 0;

    while ( zero < n && one < n)
    {
        if(a[zero] != 0 && a[one] != 1)
        {
            swap(a[zero],a[one]);
        }

        if(a[zero] == 0)
        {
            zero=zero+2;
        }
        if(a[one] == 1)
        {
            one=one+2;
        }
    }
}
Taryn
  • 242,637
  • 56
  • 362
  • 405
Aim
  • 21
  • 1
0
#include<stdio.h>
void swap(int *p,int *q)
{
  int temp=*p;
  *p=*q;
  *q=temp;
}

int main()
{
  int a[]={0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1};
  int z=0,o=1,i;
  while(z<17&&o<17)
  {
    if(a[z]==1&&a[o]==0)
        swap(&a[z],&a[o]);
    if(a[z]==0)
        z+=2;
    if(a[o]==1)
        o+=2;
  }
  if(z<17&&a[z]==1)
  {
    while(z<15)
    {
        swap(&a[z],&a[z+2]);
        z+=2;
    }
  }
  if(o<17&&a[o]==0)
  {
    while(o<15)
    {
        swap(&a[o],&a[o+2]);
        o+=2;
    }
  }
  for(i=0;i<17;i++)
    printf("%d ",a[i]);
}
Qiu
  • 5,651
  • 10
  • 49
  • 56
Archana
  • 57
  • 7
0

since it's only 1 and 0 you can just count the difference of their amount and sorting will be very easy:

int size = arr.length();
int diff = 0, i;
for(i = 0; i < size; i++) // put 0 in odd places and 1 in even and count the extra changes
    if(i % 2 == 0)
        if(arr[i] == 1){
            arr[i] = 0;
            diff++;
        }
    else
        if(arr[i] == 0){
            arr[i] = 1;
            diff--;
        }
for(i--; diff != 0; i--){ //make the tail
    if(diff > 0) //if we owe 1's put in on 0's
        if(arr[i] == 0){
            arr[i] = 1;
            diff--;
        }
    if(diff < 0) //if we owe 0's put in on 1's
        if(arr[i] == 1){
            arr[i] = 0;
            diff++;
        }
}

it's easy to see why it's correct so i won't explain. Time complexity: O( arr.length() ) or O(n)

MoonBun
  • 4,322
  • 3
  • 37
  • 69