Popular Posts

Friday, July 22, 2011

Even and Odd numbers Partition


Given an array A[], write a function to separate even and odd numbers (i.e., put all even numbers first than odd numbers) and stability is also maintain for the elements in the Array.
Eg.
input:
A[] = {12, 34, 45, 9, 8, 90, 3}   
output:                                
A[] = {12, 34, 8, 90, 45, 9, 3}  (OR)  {12 , 34,  90,  8,  9,  45,  3}

We can do it by using QuickSorting approach.But it requires one traversal across array elements.So it is O(n) approach.
private static void partitionArray(int[] a) {
int i = 0;
int j = a.length - 1;
while (i < j) {
while (a[i]%2==0)
i++;
while (a[j]%2==1)
j--;

if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
}

Refer : http://www.geeksforgeeks.org/archives/7897

No comments:

Post a Comment