Classify or segregate array containing even & odd numbers in java (example)

• Given an array containing even and odd number in java.
• We would like to classify the even and odd numbers.
  • Evens numbers should come in left side of array and odd should come in right side of array (or vice versa).
• Suppose we would like to segregate to segregate array shown in Fig 1.

Algorithm to classify even & odd numbers in an array using java

1. Take two indexes low and high [Shown in Fig 2].
   • low index points lowest position of array (low = 0).
   • high index points to highest position of array (high = array’s length – 1).
2. Increments low index till, we find odd number.
   • Stop, when we found out odd number.
3. Decrements high index till, we find even number.
   • Stop, when we found out even number.
4. Now swap the values pointed by low and high index (odd number and even number).
   • After swapping, even number will come in left side of array and odd number will be come in right side of array.
5. After performing the above algorithm, whole array will be classified into even and odd numbers.

Step 1:  

• Take two variables, low points zeroth index of array and high points to array’s length -1.

Step 2:

• Increments low index till, we find odd number and stop there
• Decrements high index till, we find even number and stop there
• Swap the values pointed by low and high index.
  • Even number will come in the left side of array and odd will come on the right side of array

Step 3:

• After step 2, we will get the array as shown in Fig 4.
• We will repeatedly keep on performing step 2, till we get the classified array.

Step 4:

• After performing above steps, we will get the array as shown in Fig 5.

Time complexity of algorithm is O (n).

Program – segregate array containing even & odd numbers in java

import java.util.Arrays;

public class SegregateEvenAndOdd {
	public static void main(String[] args) {
		int[] arr = { 10, 11, 20, 31, 50, 61, 90 };
		segregateArray(arr);
		System.out.println("Segregated array is : "+Arrays.toString(arr));
		
	}
	private static void segregateArray(int[] arr) {
		
		int low = 0;
		int high = arr.length - 1;
		
		while(low < high) {
			//increment till we find 1
			while(arr[low]%2 == 0 && low < high)
				low ++;
			
			//decrement till we find 0
			while(arr[high]%2 != 0 && low < high)
				high--;
			
			if(low < high) {
				//Swap 
				int temp = arr[low];
				arr[low] = arr[high];
				arr[high] = temp;
				low ++;
				high--;
			}
		}
		return;
	}
}

Output- classify even & odd numbers in array

Segregated array is : [10, 90, 20, 50, 31, 61, 11]