2-color smoothing

Question

I have an array containing a mixture of 0 and 1 s. I want to reorder the contents of the array so that the largest possible number of even positions in the array contains 0 , and the odd positions contain 1 as much as possible, provided that the numbers 0 and 1 not changed. This means that if the number 0 exceeds the number 1 or vice versa, then at the end of the rearranged array there will be a block consisting of all- 0 or all- 1 s. How can I do this in one go by modifying the array in place?

For instance:

 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} 

Answer 1

To do this, you can use the standard two-color sorting algorithm; just edit the array references to match access to the first half of the array with even elements in your actual array and get access to the second half of the array to odd elements in your actual array (back). Basically, a[i] becomes (provided that size even):

 a[i < size/2 ? i * 2 : (size - i) * 2 - 1] 

Answer 2

I do not think that this can be done in 1 pass, if only "leaving them where they are" means "no matter where they end."

Here is 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 is different then the number of 1 */ if (n % 2) return; /* 1st pass */ while (nn--) s += *ptr++; /* if there are as many 0 as 1 */ if (s+s == n) { /* 2nd pass */ for (nn = 0; nn < n; nn += 2) { arr[nn] = 0; arr[nn + 1] = 1; } } } 

Answer 3

Scroll through the array, preserving the invariants for the three variables and the array:

• everything was sorted to pos .
• color is the color of the item to be placed in pos .
• everything between pos and next has the same color.
• an array is a permutation of itself.

In any case, this 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 

Answer 4

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

Answer 5

It will do it. The result differs from the proposed output, but it is equal to the given rules (the text of the problem does not include the word "sort", only in the end you need to move all 0 , you can even positions and 1 you can in odd positions. You do not need to "compact" them). It's a little harder to do this "compaction".

 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 odds and a stack of even elements that need moving, and I use them when I need an even / even number. Two stacks are stored in the input array, so there is no additional space (except for two "heads" of two stacks, which are two additional integers). I think the worst case is O(1.5n) for time (for example, all elements are 1 , half of the elements are “pushed” on the stack, and then it needs to be discarded because there was no 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} 

Answer 6

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

Answer 7

This can be done in one go.

Here's another solution using one pass. The idea is to save the two indices pos_0 and pos_1 , which contains the place where the next 0 or 1 will be placed in the array. i will be used to move around 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; } } } } 

Answer 8

since this is only 1 and 0, you can just calculate the difference in their number, and sorting will be very simple:

 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 put in on 0's if(arr[i] == 0){ arr[i] = 1; diff--; } if(diff < 0) //if we owe 0 put in on 1's if(arr[i] == 1){ arr[i] = 0; diff++; } } 

it’s easy to understand why this is right, so I won’t explain. Difficulty of time: O (arr.length ()) or O (n)

Answer 9

 #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]); }