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