Sort all even numbers in ascending order and then sort all odd numbers in Descending order Java

Question

Given an array of integers (both odd and even), the task is to sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.

Examples:

Input  : 

A[] = {1, 2, 3, 5, 4, 7, 10} 

Output : 

A[] = {7, 5, 3, 1, 2, 4, 10}

Input  : 

A[] = {0, 4, 5, 3, 7, 2, 1} 

Output : 

A[] = {7, 5, 3, 1, 0, 2, 4} 

Input:

The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the array. The next line contains N space separated values of the array.

Output:

For each test case in a new line print the space separated values of the new transformed array.

Constraints: 

1<=T<=100 

1<=N<=100 0

0<=A[]<=100

Example:

Input:

2 7
1 2 3 5 4 7 10 7 0 4 5 3 7 2 1

Output:

7 5 3 1 2 4

10 7 5 3 1 0 2 4

My approach:

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class GFG {

    private static List<Integer> sortListOrder (List<Integer> list) {
        List<Integer> oddList = new ArrayList<>();
        List<Integer> evenList = new ArrayList<>();


        for (Integer elem : list) {
            if (elem%2 != 0) {
                oddList.add(elem);
            }
            else {
                evenList.add(elem);
            }
        }
        Collections.sort(evenList);
        Collections.sort(oddList);
        List<Integer> reversedList = new ArrayList<>();
        for (int i = oddList.size() - 1; i >= 0; i--) {
            reversedList.add(oddList.get(i));
        }

        reversedList.addAll(evenList);

        return reversedList;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int numTests = sc.nextInt();

        while(numTests-- > 0) {
            int size = sc.nextInt();
            List<Integer> list = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                int elem = sc.nextInt();
                list.add(elem);
            }

            List<Integer> sortedList = sortListOrder(list);

            for (Integer elem : sortedList) {
                System.out.print(elem + " ");
            }
            System.out.println();

        }
        sc.close();
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

Reference

Answer 1

You already dug into the standard library a bit (which is good) and discovered the beautiful sort method. Using this method is a perfect start.

What you overlooked is, that there is an overloaded second version of sort which accepts a comparator, so that you can perform all kinds of custom sorting with a single call.

Thus, instead of splitting the list in even and odd parts, sorting them separately, reversing one part, gluing it all back together, you could simply have created a comparator which encapsulates the logic, passed this into the sort method, and be done.

(BTW: even if you take your approach, reversing a list should be done with Collections.reverse())

So: create a comparator, do it all in a single sort call, and I look forward to see your revamped solution here in a day or so. And while you are at it: "GFG" is not an acceptable class name: what does that class do? Give it a name worth remembering!

Answer 2

Your approach is quite reasonable. Separate the data, process them separately, and combine them at the end. Can we improve the code? Absolutely. Can space and time be improved? Yes, to a point.

---

You open a Scanner at the start, and manually .close() it at the end. This is error-prone. If sc.nextInt() raises an exception due to illegal input, this block of code will exit without reaching the .close() statement, and the scanner will be left open. It is better to use a try-with-resources statement to open Closeable resources, and have the resource closed properly whether or not the block completes normally or raises an exception.

    try(Scanner sc = new Scanner(System.in) {
        // Use the scanner here
    }
    // Scanner is automatically closes when execution exits the above block.

---

Storage space:

        int size = sc.nextInt();
        List<Integer> list = new ArrayList<>();

An ArrayList<> is a fantastic storage container. You can add items to it, and it will automatically grow as needed. But it can be inefficient in two ways.

First, although it will grow as required, this regrowth is both time-consuming and memory consuming. It takes time to allocate the memory, and additional time to copy entries from the original to the new storage area. If each reallocation doubles the storage space, then during the regrowth at least 50% extra space is allocated; reallocating the storage from 100 to 200 entries temporarily requires 100+200=300 entries of space! Finally, if only 101 storage locations were actually needed, if not explicitly freed by the application, the extra 99 entries remain allocated.

This is all completely unnecessary. You've just read in the number of values the ArrayList<> will contain. Why not use that value to precisely allocate an ArrayList<> of the proper capacity?

        int size = sc.nextInt();
        List<Integer> list = new ArrayList<>(size);

No reallocations. No wasted space. Except...

The second inefficiency comes from storing primitive types in generic containers. You can't just store an int, the value has to be first "boxed" into an Integer object, which takes both time and additional memory.

Since you are storing int values, and the exact number is known ahead of time, the advantages of the flexibility of ArrayList<> are not needed. This could be done with an int[] array.

        int size = sc.nextInt();
        int[] list = new int[size];

        for (int i = 0; i < size; i++) {
            list[i] = sc.nextInt();
        }

Since Integer objects are not being stored, this takes significantly less memory, and creates only one heap object, instead of size+1 heap objects. It is also faster, since access an array doesn't required the overhead of the add() or get() function calls.

---

Similar comments will, of course, apply to the sortListOrder() method. While you don't know the number of elements which will be stored in either oddList or evenList, you do know the maximum: when all the numbers are odd or even. You can pre-allocate for this worst case:

    List<Integer> oddList = new ArrayList<>(list.size());
    List<Integer> evenList = new ArrayList<>(list.size());

While each list may be larger than needed, we know exactly \$O(2N)\$ memory is required. The advantage here is time; no ArrayList<> resizing is required.

You sort the evenList. No complaints there.

You sort the oddList. And then you reverse the list the hard way, by allocating yet another ArrayList<> without pre-sizing it (new ArrayList<>(list.size()) since you end up adding the even numbers into it as well), iterating over oddList, and .add()-ing the items one-at-a-time.

Better (as mentioned by @mtj) would be using Collections.reverse(oddList); to reverse oddList in-place without creating another temporary list.

Perhaps even better would be to sort the list using a comparator which produced the list in reverse order:

    Collections.sort(oddList, Collections.reverseOrder());

Then, the sorted even list is appended to the reverse sorted odd list, using .addAll(). Finally, the result is returned using return reversedList;, which is odd because the function is supposed to be sorting a list of numbers, not reversing them, so perhaps a better variable name is in order.

---

Can we improve this further? Certainly. This can be done in-place, with no additional storage required.

• partition the list into k odd elements at the start, and N-k even elements at the end.
• sort the sublist of odd elements list.subList(0, k) using Collections.reverseOrder().
• sort the sublist of even elements list.subList(k, N)

No joining of the two sorted lists is required, because the lists were never separated.

Alternately, it can be done with a custom sort operation, which sorts:

• an odd number always "less than" an even number,
• if both numbers are even: in ascending order
• if both numbers are odd: in descending order

Or it can be done using appropriate preprocessing and post processing, to achieve the desired ordering. For instance, convert all odd numbers to negative numbers, sort in the list in ascending order, and then turn the negative numbers back into positive ones. For example, done using a Stream:

jshell> IntStream.of(0, 4, 5, 3, 7, 2, 1).
   ...>    map(i -> i%2 != 0 ? -i : i).      // 0, 4, -5, -3, -7, 2, -1
   ...>    sorted().                         // -7, -5, -3, -1, 0, 2, 4
   ...>    map(Math::abs).                   // 7, 5, 3, 1, 0, 2, 4
   ...>    toArray();
$1 ==> int[7] { 7, 5, 3, 1, 0, 2, 4 }

Answer 3

I'd say your solution works well, but if you wanted to do it quicker, you could write a custom comparator and complete the entire task with one sort:

Collections.sort(list, (o1, o2) -> 
    o1%2 == o2 % 2 ? 
    (o2*(2*(o1%2)-1)) - (o1*(2*(o2%2)-1)) 
    : (o2%2) - (o1%2)
);

The comparator checks if both numbers are either equal or odd, and sorts odd numbers in reverse. If one number is odd and one is even, the odd one is counted as being smaller. Works like a charm.

Edit:

After some downvotes, I decided to refactor the code into something more readable:

public static int compareElements(Integer o1, Integer o2) {
    if ((o1 % 2) != (o2 % 2)) { // one even, one odd
        if (o1 % 2 == 1) { // first one is odd
            return -1;
        } else { // second one is odd
            return 1;
        }
    } else if (o1 % 2 == 0) { // both even
        return o1.compareTo(o2);
    } else { // both odd
        return o2.compareTo(o1);
    }
}

This can then be called by:

Collections.sort(list, (o1, o2) -> compareElements(o1, o2));

It does the same thing as the code above. It ensures that odd elements are always to the left of even elements, that odd elements are sorted in descending order, and that even elements are sorted in ascending order.