Sorting an array of 0’s , 1’s and 2’s

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}

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

Three flags should be used for pointing the last of 0, the last of 1, and the first of 2.

 

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–

[gist https://gist.github.com/vishnujayvel/6050043]

 

source: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Swapping every pair of nodes in a single linked list

Provided n1->n2->n3->n4->n5
in general for each pair starting with n
have a temp variable that will keep copy of reference to n.next

Consider the link list n1->n2->n3->……

and n=n1
temp=n.next             //temp=n2
n.next=n.next.next//n1.next=n1.next.next=n3

temp.next=n          //n2.next=n1

Now move n to n.next//n=n1.next=n3
Repeat the same for next pair.but we have to link previous pair with the current pair
Which will have previous pairs 2nd element ? its temp.next
So make temp.next.next=n.next

Thats it!!

 

Also you can swap the pairs by just swapping the value.That is way too simple.Look at the 2nd function
Source code:

[gist https://gist.github.com/vishnujayvel/6049904]

Given an Array A[], find the maximum j – i such that A[j] > A[i]. For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1) Time Complexity should be less then O(n^2)

	/*
	* Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
	*
	* Solution :
	* Create 2 arrays
	* 1)LeftMin : stores the minimum element to the left of arr[i] including arr[i]
	* 2)RightMax : stores the maximum element to the right of arr[i] including arr[i]
	* Initialize maxDiff=-1
	* Create a loop comparing leftMin[i] and RightMax[j] starting with i=0 and j=0 till i or j reaches n
	* If LeftMin[i]>RightMax[j]{
	maxDiff=max(maxDiff,j-i)
	* j++
	* }
	* else
	* i++
	*
	* maxDiff holds the maximum j-i
	*/
	#include<iostream>
	using namespace std;
	int max(int a,int b){
	if(a>b)
	return a;
	else
	return b;
	}
	int min(int a,int b){
	if(a>b)
	return b;
	else
	return a;
	}
	int findMaxDiff(int arr[],int n){
	int LeftMin[n];
	int RightMax[n];
	LeftMin[0]=arr[0];
	for(int i=1;i<n;i++)
	LeftMin[i]=min(LeftMin[i-1],arr[i]);
	RightMax[n-1]=arr[n-1];
	for(int i=n-2;i>=0;i--)
	RightMax[i]=max(RightMax[i+1],arr[i]);
	int i=0;
	int j=0;
	int maxDiff=-1;
	while(i<n&&j<n){
	if(LeftMin[i]<RightMax[j]){
	maxDiff=max(maxDiff,j-i);
	j++;
	}
	else
	i++;
	}
	return maxDiff;
	}
	int main(){
	int arr[]={34, 8, 10, 3, 2, 80, 30, 33, 1};
	int n = sizeof(arr)/sizeof(arr[0]);
	int maxDiff = findMaxDiff(arr, n);
	cout<<maxDiff;
	return 0;
	}

view raw findmaxidexdiff.cpp hosted with ❤ by GitHub