Menu
Is it possible to arrange the array made up of only 1's and 0's in descending order within one parse without using auxiliary array?
For example: Suppose you have an array a[]={1,0,0,0,1,0,1}, for this the expected output will be a[]={1,1,1,0,0,0,0}.
I have written the below C code but it finds the solution in 2 parses. Could it be optimized?
void arrange(int a[],int n) {
int i,count=0;
for(i=0;i<n;i++) {
if(a[i]==1)
count++;
a[i]=0;
}
for(i=0;i<count;i++) {
a[i]=1;
}
}
889
Given an integer array containing 0 and 1. We would like to sort input array. Zeros will be left end of array and one will be in right end of array. Suppose, we would like to sort an input array, as shown in Fig 1. After performing above algorithm, whole array will be sorted in O (n) times.
Take two variables, low points zeroth index of array and high points to array’s length -1. After step 2, we will get the array as shown in Fig 4. We will repeatedly keep on perform step 2 till we get the sorted array.
You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array [Basically you have to sort the array]. Traverse array only once. Recommended: Please solve it on “ PRACTICE ” first, before moving on to the solution. Thanks to Naveen for suggesting this method. 1) Count the number of 0s.
Take two pointer type0 (for element 0) starting from beginning (index = 0) and type1 (for element 1) starting from end (index = array.length-1). 2. It is intended to Put 1 to the right side of the array. Once it is done, then 0 will definitely towards the left side of the array.
for (size_t i = 0, count = 0; i < n; i++) {
if (a[i] == 1) a[count++] = 1;
if (i >= count) a[i] = 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
