Segregate os and 1s in an array

Variation 1: Segregate os and 1s in an 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. Traverse array only once.

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

http://www.geeksforgeeks.org/segregate-0s-and-1s-in-an-array-by-traversing-array-once/

Variation 2: Segregate Even and Odd numbers

Keep two pointers one at beginning and other at end.Move begin pointer until it meets 

with an even number and move end pointer towards left until it meets with an odd number.

Then swap the two values and continue.Continue this way until begin and end pointers 

cross each other.

http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/

Variation 3: Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example

Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};

Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

Variation 4:

Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's.   The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array.
Example:   Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3.

Note: You just need  to complete the function given  below for this task. The function is given a binary string as input and returns the required answer.

Variation 4.1
Given a linked list that contains 0,1 and 2 . Sort this linked such that it contains 0s first, then 1s and then 2s in O(n) time. Remember its a linked list not an array.

Hint: We can remain at one previous node & compare the values.Then we swap as per Dutch flag algo.
http://www.geeksforgeeks.org/sort-a-linked-list-of-0s-1s-or-2s/
Variation 5:
Given an array of integers, {1,0,2,0,3,0,0,4,5,6,7,0,0,0}, you have to create a new array which will be like (1,2,3,4,5,6,7,0,0,0,0,0,0,0}, without using any other temporary array.

Code :Variation 1-Two Pointer Approach

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void segregate0and1(int arr[], int size)
{
//Two Pointers one from front and other from back
int left = 0, right = size-1;

while(left < right)
 {
   /* Increment left index while we see 0 at left */
   while(arr[left] == 0 && left < right)
   left++;

   /* Decrement right index while we see 1 at right */
   while(arr[right] == 1 && left < right)
   right=right-1;

  /* If left is smaller than right then there is a 1 at left
  and a 0 at right. Exchange arr[left] and arr[right]*/
   if(left < right)
  {
    arr[left] = 0;
    arr[right] = 1;
    left++;
    right=right-1;
  }
 }

}

int main()
{
int arr[] = {1,1, 1,0,0,0};
int arr_size = 6, i = 0;

segregate0and1(arr, arr_size);

printf("array after segregation ");
for(i = 0; i < 6; i++)
printf("%d ", arr[i]);

getchar();
return 0;
}

Variation 2:

#include <iostream>
#include<string.h>

using namespace std;
int swapSort(string s) {
    int res = 0;
    int len = s.length();
    int i= len -1;
    while(s[i--] == '1');
    int c = i + 1, c1= 0;
    for(;i>=0;i--) {
        if(s[i] == '1') {
           res += c-i-c1;
           c1++;
        }
    }
    return res;
}

int main(){

    string e;
 cout << "Enter a string:" << endl;
 cin >> e;
   // int l=swapSort(e);
 cout << "The total number of swaps required is: "<< swapSort(e)<< endl;
 system("pause");

 return 0;
}

Variation 3:

Concept------
Dutch National Flag Algorithm, or 3-way Partitioning —

Part way through the process, some red, white and blue elements are known and are in the “right” place. The section of unknown elements, a[Mid..Hi], is shrunk by examining a[Mid]:

|
0 0 0 1 1 1 ? ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi

Examine a[Mid]. There are three possibilities: a[Mid] is (0) red, (1) white or (2) blue.
Case (0) a[Mid] is red, swap a[Lo] and a[Mid]; Lo++; Mid++

0 0 0 0 1 1 1 ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi

Case (1) a[Mid] is white, Mid++

0 0 0 1 1 1 1 ? ? ? 2 2 2
^ ^ ^
| | |
Lo Mid Hi

Case (2) a[Mid] is blue, swap a[Mid] and a[Hi]; Hi–

0 0 0 1 1 1 ? ? ? 2 2 2 2
^ ^ ^
| | |
Lo Mid Hi

Continue until Mid>Hi.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;

while(mid <= hi)
{
switch(a[mid])
{
case 0:
swap(&a[lo++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[hi--]);
break;
}
}
}

void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main()
{
int arr[] = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
int i;

sort012(arr, arr_size);

printf("array after segregation ");
printArray(arr, arr_size);

getchar();
return 0;
}
Output Flow:
when case 0: low=0 mid=0
when case 1: mid=2
when case 1: mid=3
when case 0: low=1 mid=3
when case 1: mid=5
when case 2: mid=5 high=11
when case 1: mid=6
when case 1: mid=7
when case 2: mid=7 high=10
when case 0: low=2 mid=7
when case 0: low=3 mid=8
when case 0: low=4 mid=9
array after segregation 0 0 0 0 0 1 1 1 1 1 2 2

Variation 4:

#include <stdio.h>
#include <stdlib.h>

void zeroatend(int a[], int n)
{
    int i = 0, j = 0;

    for(j = 0; j < n; ++j)
    {
        if(a[j])
            a[i++] = a[j];
    }

    while(i < n)
        a[i++] = 0;
}



int main()
{
    int n;

    scanf("%d", &n);

    int a[n];
    int i;

    for(i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
    }

    zeroatend(a, n);

    for(i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}