Array Even Odd Sorting LeetCode (Segregate Even and Odd Numbers)

Given an array of integers, write a method to organize it in a way that all even numbers come in the beginning and all the odd numbers come in the end. Can you try without additional storage?
 

This problem is popular in LeetCode and GeeksForGeeks A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions
 

Approach:

1. create two pointers p1 and p2. p1 points to begining of the array and p2 to the end
2. repeat while p1<p2 
1. if index p1 has even element, increase p1 
2. if index p2 has odd element, decrease p2 
3. if index p1 has odd element
1. we need to send it to right by swapping with the even item on right 
4. if index p2 has even element, we need to bring it to left by swapping with the odd in the left

Solution:

	/**
	* Given an array of integers, write a method to organize it in a way that all
	* even numbers come in the begining and all the odd numbers come in the end.
	* Can you try without additional storage?
	*
	* Sol: -create two pointers p1 and p2. p1 points to begining of the array and
	* p2 to the end. -repeat while p1<p2 --if index p1 has even element, increaes
	* p1 --if index p2 has odd element, decrease p2 --if index p1 has odd element,
	* we need to send it to right by swapping with the even item on right --if
	* index p2 has even element, we need to bring it to left by swapping with the
	* odd in the left
	*/
	import java.util.Arrays;
	public class ArrayEvenOddSorting {
	public static void doEvenOddSorting(int[] arr) {
	int p1 = 0;
	int p2 = arr.length - 1;
	while (p1 < p2) {
	if (arr[p1] % 2 == 0) {//is even
	p1++;
	}
	if (arr[p2] % 2 != 0) {//is odd
	p2--;
	}
	if (arr[p1] % 2 != 0 && arr[p2] % 2 == 0) {
	//odd is in the left point and even is in the right point, so swap them
	int temp = arr[p1];
	arr[p1] = arr[p2];
	arr[p2] = temp;
	//advance the pointers
	p1++;
	p2--;
	}
	}
	}
	public static void main(String args[]) {
	int[] arr = {1, 2, 5, 7, 0, 9, 12, 11};
	doEvenOddSorting(arr);
	System.out.println("after sorting:" + Arrays.toString(arr));
	}
	}

view raw ArrayEvenOddSorting.java hosted with ❤ by GitHub

	public class ArraysEvenOddSorting {
	/**
	* Have one index pointing at start of array as the even index and another
	* at the end of the array as the odd index.
	* 1)repeat while evenindex < oddindex
	* 1 a) If a[evenindex] is even advance the evenindex(evenindex++)
	* 1 b) if a[oddindex] is odd advance the odd index (oddindex--)
	* 1 c) If a[evenindex] is odd, swap a[evenindex] with a[oddindex]
	* 1 d) if a[oddindex] is even, swap a[oddindex] with a[evenindex]
	*
	* Complexity: O(n)
	* Space: O(1)
	*
	* @param x
	* @return
	*/
	public static int[] sortEvenOdd(int[] a){
	int oddIndex = a.length-1;
	int evenIndex = 0;
	while(evenIndex<oddIndex){
	if(a[evenIndex]%2==0){ //is even
	evenIndex++;
	}else{
	int temp = a[oddIndex];
	a[oddIndex] = a[evenIndex];
	a[evenIndex] = temp;
	oddIndex--;
	}
	/*
	if (a[oddIndex]%2==0){ //is even
	int temp = a[oddIndex];
	a[oddIndex] = a[evenIndex];
	a[evenIndex] = temp;
	}else{
	oddIndex--;
	}
	*/
	}
	return a;
	}
	public static void main(String args[]){
	int[] a ={12,2,4,7,9};
	System.out.println("before sorting\n");
	for(Integer aa:a){
	System.out.print(aa+",");
	}
	a = sortEvenOdd(a);
	System.out.println("\n");
	System.out.println("after sorting\n");
	for(Integer aa:a){
	System.out.print(aa+",");
	}
	System.out.println();
	}
	}

view raw ArrayEvenOddSortingII.java hosted with ❤ by GitHub