Sort all the even numbers in ascending order, and then sort all the odd numbers in descending order in the collection

Question

This is an interview question.

There are some random numbers (say, in an integer array).

• How can we sort all the even numbers in ascending order, and then sort all the odd numbers in descending order.
• which collection is best suited.

Input Numbers:

12 67 1 34 9 78 6 31 

The result is saved in the collection:

 6 12 34 78 67 31 9 1 

Answer 1

Any collection that supports sorting using custom matching will do - even an array. Add your own comparator as follows:

 public int compare(int x, int y) { if (x&1 == y&1) { // Both numbers are odd or both numbers are even if (x&1 == 0) { // Both numbers are even: compare as usual return Integer.compare(x, y); } else { // Both numbers are odd: compare in reverse return Integer.compare(y, x); } } // One is odd, the other one is even if (x&1 == 0) { return -1; } return 1; } 

Answer 2

You can do the following:

 public ArrayList<Integer> sort(Integer[] input) { int length = input.length; ArrayList<Integer> oddNumber = new ArrayList<Integer>(0); ArrayList<Integer> evenNumber = new ArrayList<Integer>(0); for (int i = 0; i < length; i++) { Integer val = input[i]; if(isEven(val)){ evenNumber.add(val); } else { oddNumber.add(val); } } Collections.sort(evenNumber); Collections.sort(oddNumber, Collections.reverseOrder()); evenNumber.addAll(oddNumber); return evenNumber; } public boolean isEven(Integer x) { return x % 2 == 0; } 

EDIT

I implemented a comparator based on the Jesper algorithm.

 public ArrayList<Integer> sort(Integer[] input) { ArrayList<Integer> output = new ArrayList<Integer>(0); output.addAll(Arrays.asList(input)); Collections.sort(output, new EvenOddComparator()); return output; } public class EvenOddComparator implements Comparator<Integer> { final int BEFORE = -1; final int EQUAL = 0; final int AFTER = 1; @Override public int compare(Integer o1, Integer o2) { if (o1 % 2 == 0 && o2 % 2 != 0) { return BEFORE; } else if (o1 % 2 != 0 && o2 % 2 == 0) { return AFTER; } else if (o1 % 2 == 0 && o2 % 2 == 0) { return o1.compareTo(o2); } else if (o1 % 2 != 0 && o2 % 2 != 0) { return o2.compareTo(o1); } return EQUAL; } } 

Greetings.

Answer 3

If you do not need you to implement the entire sorting algorithm yourself, you can simply use Collections.sort(list, comparator) , and you will need to provide your own implementation of Comparator<Integer> , which compares the numbers and returns the result so that the numbers are sorted in order defined by the rules.

The comparator would have to follow these rules:

• If the first number is even and the second number is odd, return -1 (because even numbers must arrive before the odd numbers).
• If the first number is odd and the second is even, return 1 (because even numbers must arrive before the odd numbers).
• If both numbers are even: Compare both numbers, return -1 if first <second, 0 if it is equal, 1 if first> second (sorts even numbers in ascending order).
• If both numbers are odd: Compare both numbers, return 1 if first <second, 0 if equal, -1 if first> second (sorts odd numbers decreasing).

If you have numbers in the array instead of List , use Arrays.sort(array, comparator) .

Answer 4

Here is the code:

 @Override public int compare(Integer o1, Integer o2) { if (o1 % 2 ==0) { if (o2 % 2 == 0) { if (o1 < o2) return -1; else return 1; } //if (o2 % 2 != 0) else { return -1; } } else { if (o2 % 2 != 0) { if (o1 < o2) return 1; else return -1; } //if (o2 % 2 == 0) else { return 1; } } } 

Answer 5

package com.java.util.collection;

import java.util.Arrays; import java.util.Collections;

public class EvenOddSorting {

 public static void eventOddSort(int[] arr) { int i =0; int j =arr.length-1; while(i<j) { if(isEven(arr[i]) && isOdd(arr[j])) { i++; j--; } else if(!isEven(arr[i]) && !isOdd(arr[j])) { swap(i,j,arr); } else if(isEven(arr[i])){ i++; } else{ j--; } } display(arr); // even number sorting Arrays.sort(arr,0,i); insertionSort(arr,i,arr.length); // odd number sorting display(arr); } /** * Instead of insertion sort, you can use merge or quick sort. * @param arr * @param firstIndex * @param lastIndex */ public static void insertionSort(int[] arr, int firstIndex, int lastIndex){ for(int i=firstIndex+1;i<lastIndex;i++){ int key =arr[i]; int j=i-1; while(j>=firstIndex && key > arr[j]) { arr[j+1] = arr[j]; arr[j] =key; j=j-1; } System.out.println("\nAfter "+(i+1) +" Iteration : "); display(arr); } } public static void display(int[] arr) { System.out.println("\n"); for(int val:arr){ System.out.print(val +" "); } } private static void swap(int pos1, int pos2, int[] arr) { int temp = arr[pos1]; arr[pos1]= arr[pos2]; arr[pos2]= temp; } public static boolean isOdd(int i) { return (i & 1) != 0; } public static boolean isEven(int i) { return (i & 1) == 0; } public static void main(String[] args) { int arr[]={12, 67, 1, 34, 9, 78, 6, 31}; eventOddSort(arr); } 

}

Answer 6

I do not think that one collection is necessarily better than another; I would use something that extends the list, not the collection, although it is definitely not a map.

What I would do is that in my Collection.sort call I would check if the mod 2 number%2 ( number%2 ) is equal, but I would do a simple compareTo , otherwise I would do Integer.MAX_INT - oddNumber and then do comparison. Thus, the larger the odd number, the smaller the number generated, and it will be sorted to the end of the list in descending order.

 Integer num1 = (o1%2 == 0)? new Integer(o1) : new Integer(Integer.MAX_INT - o1); Integer num2 = (o2%2 == 0)? new Integer(o2) : new Integer(Integer.MAX_INT - o2); return num1.compareTo(num2); 

The above is just sudo code, don't take it too literally, just to give you an idea.

Answer 7

If all numbers are positive, you can multiply your odd numbers by -1, do a standard sort, and then multiply all odd numbers again by -1.

If you need an order, as in the question, you will also have to swap the "negative" and "positive" arrays before the 2nd multiplication.

General Overhead: Three more cycles in addition to the selected sorting algorithm.

 List<Integer> numbers = new ArrayList<Integer>(); //add some numbers here //12 67 1 34 9 78 6 31 <-- in the list for (int i = 0; i < numbers.size(); i++) { if (numbers.get(i) % 2 == 1) { numbers.set(i, numbers.get(i) * (-1)); } } //12 -67 -1 34 -9 78 6 -31 <-- before sort sort(numbers); //-67 -31 -9 -1 6 12 34 78 <-- after sort swapNegativeAndPositiveParts(numbers); //6 12 34 78 -67 -31 -9 -1 <-- after swap for (int i = 0; i < numbers.size(); i++) { if (numbers.get(i) % 2 == 1) { numbers.set(i, numbers.get(i) * (-1)); } } //6 12 34 78 67 31 9 1 <-- after second multiplication 

Answer 8

You can use one data structure that contains all numbers, and then create two SortedSet s, one for odd and one for even. A sorted set can take a Comparator as a parameter that allows you to sort items during data entry.

After that, you will go through all the numbers, create a new collection that combines two sorted sets.

You can also replace sorted sets with two Lists . After that, you added all the numbers, call Collections.sort() in the lists, and then merge as before.

Answer 9

Ad1. We need to create a Comparator<Tnteger> that works with these rules.

• If we compare an even number with an odd number, then even always more.
• If we compare two odd numbers, the result will be as we would like to sort the sort.
• If we compare two even numbers, the result will be the same as we would like to sort.

Ad2. I do not understand.

Answer 10

Like this:

 var list = new List<int>{1,5,2,6,3,9,10,11,12}; var sorted = list.Where (l => l%2 ==0).OrderBy (l=>l).Union(list.Where (l => l%2 != 0).OrderByDescending (l=>l)); 

Answer 11

I would normalize all the numbers and then sort them.

 public static void main(String[] args) { int[] values = {Integer.MIN_VALUE, 0, Integer.MAX_VALUE - 1, Integer.MIN_VALUE + 1, -1, 1, Integer.MAX_VALUE}; for (int i = 0; i < values.length; i++) { int value = encode(values[i]); assert decode(value) == values[i]; values[i] = value; } Arrays.sort(values); for (int i = 0; i < values.length; i++) // give back the original value. values[i] = decode(values[i]); System.out.println(Arrays.toString(values)); } private static int decode(int value) { return value >= 0 ? Integer.MAX_VALUE - (value << 1) : Integer.MIN_VALUE + (value << 1); } private static int encode(int value) { return (value & 1) == 0 ? (value >> 1) + Integer.MIN_VALUE / 2 : Integer.MAX_VALUE / 2 - (value >> 1); } 

prints

 [-2147483648, 0, 2147483646, 2147483647, 1, -1, -2147483647] 

An additional bias occurs here, so very large numbers are not distorted. (therefore the number is divided by two)

Answer 12

I just coded a quick example as shown below:

 public class CustomSorting { public static void main(String[] args) { Integer[] intArray = new Integer[] {12, 67, 1, 34, 9, 78, 6, 31}; Arrays.sort(intArray, new Comparator() { @Override public int compare(Object obj1, Object obj2) { Integer int1 = (Integer) obj1; Integer int2 = (Integer) obj2; int mod1 = Math.abs(int1%2); int mod2 = Math.abs(int2%2); return ((mod1 == mod2) ? ((mod1 == 0) ? int1.compareTo(int2) : int2.compareTo(int1)) : ((mod1 < mod2) ? -1 : 1)); } }); } } 

Output :

[6, 12, 34, 78, 67, 31, 9, 1]

Answer 13

in Java: - Best approach, minimal complexity

 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class EvenOddSorting { public static void main(String[] args) { // TODO Auto-generated method stub int i, size; ArrayList<Integer> listEven = new ArrayList<Integer>(); ArrayList<Integer> listOdd = new ArrayList<Integer>(); ArrayList<Integer> finalList = new ArrayList<Integer>(); Scanner sc = new Scanner(System.in); System.out.println("Enter Array Size : "); size = sc.nextInt(); int A[] = new int[size]; for (i = 0; i < size; i++) { A[i] = sc.nextInt(); } for (i = 0; i < size; i++){ if (A[i] % 2 == 0){ listEven.add(A[i]); } else if (A[i] % 2 != 0) { listOdd.add(A[i]); } } Collections.sort(listEven); Collections.sort(listOdd); Collections.reverse(listOdd); finalList.addAll(listOdd); finalList.addAll(listEven); System.out.println("Result is : "+finalList); } } 

Exit: -

Enter array size: 10

1 2 3 4 5 6 7 8 9 10 Result: [9, 7, 5, 3, 1, 2, 4, 6, 8, 10]