ObjecÂtive: Given an array which contains even and odd integers. Write an algorithm to separate even and odd numbers.
Example
int [] arrA = {1,2,3,4,6,8,7,12}; Output: [12, 2, 8, 4, 6, 3, 7, 1]
Approach: Swapping Indexes
- Use two indexes, left and right.
- Put left index at the start of array and right at the end of the array.
- Increment left till odd number is not found.
- Decrement right till even number is not found.
- Swap left and right elements
- Do it till left<right
Time Complexity: O(n)
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class OddAndEven { | |
public static int[] arrange(int [] arrA){ | |
int left =0; | |
int right = arrA.length–1; | |
while(left<right){ | |
if(arrA[left]%2==0) | |
left++; | |
else if(arrA[right]%2==1) | |
right—; | |
else{ | |
//swap left and right elements | |
int temp = arrA[left]; | |
arrA[left] = arrA[right]; | |
arrA[right] = temp; | |
left++; | |
right—; | |
} | |
} | |
return arrA; | |
} | |
public static void main(String[] args) { | |
int [] arrA = {1,2,3,4,6,8,7,12}; | |
System.out.println("Rearranging arrays using left and right indexes"); | |
arrA = arrange(arrA); | |
System.out.println(Arrays.toString(arrA)); | |
} | |
} |
Output:
Rearranging arrays using left and right indexes [12, 2, 8, 4, 6, 3, 7, 1]